yukicoder No.268 ラッピング（Easy）の感想

問題はこちら
No.268 ラッピング（Easy） - yukicoder

この問題の肝は一周の長さの配列[2(L1+L2), 2(L2+L3), 2(L3+L1)]と何色が何周するかっていう配列[R, B, Y]をどういう組合せで掛け算して足し合わせると一番小さくなるかってとこですね。
この問題は高々3 * 2 * 1 = 6通りしかないので私はとりあえず総当たりで解いちゃいましたがもっと大きくなると総当たりは計算量的にきついです。

それで、まあ何となく「大きい順にソートしたのと小さい順にソートしたのを掛け合わせて足すのが一番小さくなりそうだなー」って直感的に思いますよね。
もうちょっと一般化すると
$x_1 \leq x_2 \leq \dots \leq x_n,$
$y_1 \leq y_2 \leq \dots \leq y_n$
に対して、以下のようなことが成り立ちそうだなって思います。

任意の置換 $p \in S_{n}$ に対して
$\sum_{i = 1}^{n} x_i y_{p(i)} \geq \sum_{i = 1}^{n} x_i y_{n - (i - 1)}$

$n = 2$ のときなら話は簡単で組合せとしては $x_1 y_1 + x_2 y_2$ と $x_2 y_1 + x_1 y_2$ しかないので
$x_1 y_1 + x_2 y_2 \geq x_2 y_1 + x_1 y_2$
であることだけ示せばよいです。これは右辺を移項して
$x_1 y_1 + x_2 y_2 - (x_2 y_1 + x_1 y_2) \geq 0$
を示すとよいです。これは左辺を変形してやると
$x_1(y_1 - y_2) + x_2(y_2 - y_1) = (x_2 - x_1)(y_2 - y_1) \geq 0$
であるので確かにこの不等式が成り立っていることが分かります。

それで一般の場合に戻ると、任意の置換pをバブルソートで降順にソートすることを考えてみます。
するとバブルソートの一回の入れ替えで起きるのは２つの要素の入れ替えだけなのでこれはn = 2の場合に帰着できます。
バブルソートしていく過程で元の内積より等しいか、小さくなるかなので降順のバブルソートが終わったときも一般の不等式が成り立っていることが分かります。

……っていうことがGoogle Code Jamの過去問で出てたらしく「なるほどなぁ」って思いました。面白かったです。
Dashboard - Round 1A 2008 - Google Code Jam
解説
Dashboard - Round 1A 2008 - Google Code Jam