山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[AtCoder] A - Task Scheduling Problem

問題

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 の選び方を考えます。

①  a_1 \leq a_2 \leq \cdots \leq a_n のとき

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

 = a_n - a_1

となります。

②  a_2 \leq a_1 \leq \cdots \leq a_n のとき

 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

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

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

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