Tenka1 Programmer Contest C - Align

https://atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c

正の整数からなる数列 $\{A_i\}_i$ が与えられた時に、数列を自由に並び替えた時の隣り合う要素の差の合計の最大値を求めよ、という問題。

大小関係がジグザグにすれば良い、ということはなんとなくわかったが、解説を読んでもピンと来なかったので整理しておく。

まず、 $A_i$ はソートされていると考えて良いだろう。すると、次のような問題を考えれば良いことになる。

fig1

数直線の上に $\{A_i\}_i$ が並んでいる。始点と終点を異なるように選び、全ての点を一回ずつ通って進む。移動距離の最大値を求めよ。

$A_i$ と $A_{i+1}$ が作る区間を $I_i$ とし、その長さを $B_i = A_{i+1}-A_i$ とおく。上の図だと、 $A_1$ から $A_5$ まで点があり、区間が $I_1$ から $I_4$ まである。

始点=終点の場合を考えてみる

脱線するが、最初に始点 = 終点となる場合の変種を考える。

それぞれの区間を通過する最大回数を考える。 $I_1$ から順番に考えていくと、 $I_1$ を通過するのは $A_1$ から出ていく時か、 $A_1$ に入る時の高々2回しかない。 $I_2$ を考えると、 $I_1$ で考えた $A_1$ から出ていく矢印、 $A_1$ に戻る矢印がそのまま2を通過する場合と、新たに $A_2$ に出入りする矢印がある場合の高々4通りである。

このように考え、さらに左右の対称性も考慮すると、区間 $I_i$ を通過する回数は、最大 $2\min (i, n-i)$ 回であることがわかる。

fig2

また、この最大値をとるような動き方は、上の図のようにジグザグに移動することで必ず達成でき、 $2\sum_{i=1}^{n-1} \min (i, n-i) B_i$ が移動距離の最大値であることがわかる。

始点と終点が異なる場合

始点と終点が異なる場合、移動距離 $2\sum_{i=1}^{n-1} \min (i, n-i) B_i$ は達成できない。

fig3

しかし、上のようにジグザグに動くことを考えると、

$n = 2m-1$ , 奇数の場合 : $2\sum_{i=1}^{n-1} \min (i, n-i) B_i - B_{m-1}$ や $2\sum_{i=1}^{n-1} \min (i, n-i) B_i - B_m$
$n = 2m$ , 偶数の場合 : $2\sum_{i=1}^{n-1} \min (i, n-i) B_i - B_m$

は達成できることがわかる。それぞれ始点、終点の位置の集合は

$n = 2m-1$ , 奇数の場合 : $\{A_{m-1},A_m\}$ または $\{A_m,A_{m+1}\}$
$n = 2m$ , 偶数の場合 : $\{A_m,A_{m+1}\}$

と中央の位置にある場合になる。始点と終点が一致する時の通過回数の最大回数に比べ、通過回数の差は

$n = 2m-1$ , 奇数の場合 : $I_{m-1}$ または $I_m$ が1回少なく通過
$n = 2m$ , 偶数の場合 : $I_m$ が1回少なく通く

区間を通過する回数を始点=終点の時と同様に考えると、それ以外の位置に始点、終点がある場合通過区間の通過した回数が少なくなることがわかる。(最適な始点・終点の位置より外側に配置すると通過できない回数が増え、上に挙げたいずれかの場合よりも距離が短くなる)

結局、ジグザグに動く時が最適になり、

$n = 2m-1$ , 奇数の場合 : $2\sum_{i=1}^{n-1} \min (i, n-i) B_i - \min (B_{m-1},B_m)$
$n = 2m$ , 偶数の場合 : $2\sum_{i=1}^{n-1} \min (i, n-i) B_i - B_m$

が答えになることがわかる。

https://atcoder.jp/contests/tenka1-2018/submissions/32590060