数学/競プロメモ

Tenka1 Programmer Contest-C：Align(400)

問題

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

$n$ 要素の数列 $\{A_n\}$ が与えられる。 $A_i$ を任意の順番に並べ替えて隣接項の差の合計を最大にするとき、最大値を求めよ。

考え方

隣接項の差をなるべく大きくするには以下のように数列を並べ替える必要がある。

$a_1 \leq a_2 \geq a_3 \leq a_4 \geq ...$
$a_1 \geq a_2 \leq a_3 \geq a_4 \geq ...$

偶奇で場合分けする。偶奇で考えることは同様なので、奇数の場合のみ考える。

$N=5$ とする。考えうる数列は

$a_1 \leq a_2 \geq a_3 \leq a_4 \geq a_5$
$a_1 \geq a_2 \leq a_3 \geq a_4 \leq a_5$

である。このときの差を計算すると、それぞれ以下のようになる。

$(a_2 - a_1) + (a_2 - a_3) + (a_4 - a_3) + (a_4 - a_5)$
$(a_1 - a_2) + (a_3 - a_2) + (a_3 - a_4) + (a_5 - a_4)$

それぞれ計算すると各要素と係数の関係は以下のようになる。

$\{A_n\}$	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$a_i$ の係数	$-2$	$-1$	$-1$	$2$	$2$

$\{A_n\}$	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$a_i$ の係数	$-2$	$-1$	$1$	$1$	$2$

よって、 $\{A_n\}$ をソートして、小さい要素から順番に各係数をかけてゆけば最大値を求めることができる。

Nが奇数の場合も同様である。

ポイント

考えられる場合を考えて、立式をする（なんとなくで求めない）

類題