Tenka1 Programmer Contest　(2018) C - Align

問題
 提出コード
時間内に解きたかったですね…

解法

解説に詳しい証明が載っているのですが、並べた後の数列が凸凹になっていると、効率がよりよくなります。
$a_1 \geqq a_2 \leqq a_3 \geqq a_4 \leqq ...$ みたいな感じです(逆もあり得ます)。
このとき、以下のような図で表現できます。上にある頂点は隣の数より大きく、下にある頂点は隣の数より小さいです。
f:id:emtubasa:20181029014424p:plain

さて、このときの差の絶対値の計算はというと、
$a_1 - 2×a_2 + 2×a_3 - 2×a_4 + a_5$
となります。
$N$ が増えると、2倍して足す部分、もしくは引く部分が交互に追加されていきます。
この中で、数字をどのように使って行くのが一番いいのかというと、

より大きい数字は、2倍して加算する部分
より小さい数字は、2倍して減算する部分
となります。ただし、端の2箇所だけ、2倍されずに加算、もしくは減算される部分が存在するので、この部分だけ調整します。
これは、 $N$ この数字をソートしたとき、中央の2個(もしくは3個)の数字を見るだけで大丈夫です。これは、偶奇で場合分けをしてあげるとスッキリいきます。そして、それ以外は、先ほどの条件にしたがって先に計算してしまいます。
$N$ が奇数の場合

f:id:emtubasa:20181029015222p:plain
中央の3つだけを取り出して考えると、上記のような2パターンに絞られます。
上は $a_1 - 2×a_2 + a_3$ であり、
下は $-a_1 + 2×a_2 - a_3$ です。
先ほども述べたように、2倍して加算する部分はできるだけ大きい数字を、2倍して減算する部分はできるだけ小さい数字を選ぶのがいいので、3種類の数字を小さい順に $min, med, max$ と名付けてあげると、先ほどの2パターンそれぞれについての最大値は
$max + med-2×min$
$2×max - med - min$
となります。
あとは、この2つのうち大きい値を選んであげればよいです。