[AtCoder] A - Task Scheduling Problem - ヤマカサのプログラミング勉強日記

A問題でここまで難しいのは初めてですね。

$A_1, A_2, \cdots , A_n$

の中から、 $a_i = A_j$

$a_i \neq a_j$ ( $a_i \neq a_j$ )

となるように選びます。 $A_i$ は値が同じになる可能性がありますが、区別できるとします。

なんかうまく説明できないぞ。

ここで、次の関数を考えます。

$f(a) = |a_2 - a_1| + |a_3 - a_2 | + \cdots + |a_n - a_{n - 1} |$

$f(a)$ を最小化する $a$ の選び方を考えます。

$f(a) = (a_2 - a_1) + (a_3 - a_2) + \cdots (a_n - a_{n - 1})$

$= a_n - a_1$

となります。

$f(a) = -(a_2 - a_1) + (a_3 - a_2) + \cdots (a_n - a_{n - 1})$

$= a_n + a_1 - 2a_2$

$\gt a_n + a_2 - 2a_2 = a_n - a_2$

となるので、②の条件よりも①の方が小さい値となります。

多分以上のことを繰り返して、①と降順に並んでいるものが最小であると証明できると思うんですが、うまい証明方法が分かりません。

まあ、なんとなく分かったのでよしとしますか。