Codeforces Round #635 (Div. 2) - D. Xenia and Colorful Gems - Senの競技プログラミング備忘録

概要

n_a, n_b, n_cと長さがn_aのa, n_bのb, n_cのcが与えられる。
aの中の1つの要素をx, bの中の1つの要素をy, cの中の1つの要素をzとする。 $(x-y)^2+(y-z)^2+(z-x)^2$ を最小化せよ。

制約：　1 <= n_a, n_b, n_c <= 10^5, 1 <= a[i], b[i], c[i] <= 10^9

ACするまで

1. 何か裏がありそうな式ではあるが、なんやかんやうまく全探索でやるしかなさそう。
2. 全探索をするのならば、制約的に何かしらを固定して、そこで二分探索ぐらいなら計算量が間に合う限界。
3. 3つのものの最適化なので、真ん中を固定して考えてみる。
4. 直感的な式が出てくるけど、これを証明することで正しいことが分かる。->AC

考察

数学としてみるのならば、なかなか興味深い式だけど、コンピューター特有の「何かしらを固定しての最適化をして、固定対象を全探索」という手法は往々にして通用する。

固定するものは試行錯誤するうちに、(3個問題の最適化だし)真ん中のを固定するとうまくいくのか？と感じる。どううまくいきそうなのか？

今回の問題では、x, y, zには大小関係は設定されていない。そもそもどれが真ん中なのか？
これについては、難しい問題ではない。x<=y<=zのように、(x, y, z)の並び順はたかだか6通りしかないから、ぶっちゃけ大小関係6通り全部試せばいい。

こういうことから、ここではx<=y<=zであると条件を付けても差し支えない。
yを固定したとする。この時、xとzはどのような値が $(x-y)^2+(y-z)^2+(z-x)^2$ を最小化できそうなのか？

直感としては、x, zともにyに一番近いような値をとる、となるだろう。これが正しいかどうかは数学的に証明してみないとわからない。

証明

$(x-y)^2+(y-z)^2+(z-x)^2$ で $y$ が定数の時、 $X$ と $Z$ が $y$ に一番近い値と定める。
$x=X$ ではないときに、最適解があるとする。( $z=Z$ でないときも同様)この時、 $x=X$ にすることによって、 $(x-y)^2+(y-z)^2+(z-x)^2$ の値にどれほどの変化が生じるのだろうか？
$(元のx-y)^2-(X-y)^2$ と $(z-元のx)^2-(z-X)^2$ だけ、小さくなるとわかる。([tex: 元のX帰ってきた値(xより大きい最小の値)の1つ手前でよく、