Tenka1_2018 C - Align 解説[python]

概要

正の整数がN個与えられた時、それを並び替えて、隣あう要素との差の合計が最大になるようにした時の値を求めよ

制約

2<=N<=10**5
1<=A<=10**9

考察

Naiveな方法だと全ての並び方を全列挙して毎回差を計算することができるが、当然TLE

貪欲に考えると、大きい、小さいが交互に並んだ時が最小に見える。また両端は一度しか計算されないので、差分が小さくなる真ん中の大きさの文字を持ってくれば良さそう。

証明

背理法（階段型になっているケースで必ず交互に並び替えた方が大きくなることを示す）

　文字で説明しにくく買ったので絵を書いてみましたが、なんとか伝わるでしょうか。。（多分あってるはず。。）

証明の図

証明の説明図

　あとは、並び順と大小の準で並べるか、小大の順で並べるかを決める必要がある。

並び順

　並び順に関しては、大小を交互で並べた時、それぞれの要素a[i]に対して|a[i]-a[j] | がa[i]-a[j] になるか、a[j]-a[i]になるかは大、小どちらの区分に入るかで決まるので、2*(sum(a[i])-sum(a[j])) -(+)両端の要素(iは大区分に入る要素、j は小区分に入る要素）
　という形になる。

　大小か小大かに関しては両方計算して大きい方をとる

実装

#!/usr/bin/env python3
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
if n % 2 == 0:
    print(2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] + a[n // 2 - 1])
else:
    daishou = 2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] - a[n // 2 + 1]
    shoudai = (
        2 * (sum(a[1 + n // 2 :]) - sum(a[: 1 + n // 2])) + a[n // 2] + a[n // 2 - 1]
    )
    print(max(daishou, shoudai))

反省

　Naiveな解から貪欲な解を考えて証明するという流れは考えやすくよかった。

　40min くらいかかったが、大部分は証明を考えていた時間。
　証明に慣れることが必要かも。
　
　ただ、証明を行ってきちんと立式していたおかげ実装に手間取らなかったので、このくらいの解像度を実装前に用意することは必要そう。