ARC167-A - Toasts for Breakfast Party
これで灰色diffとはほんまARCは魔境ですわ。
まずAをsortして、N個の配列から(N-M)のペアを適当に選ぶ。そうするとN-M個のペアと、N-2*(N-M)=2M-N個のソロができる。合わせてM個。それを皿にのせる。
そのうちの2つのペアの組み合わせはAa≦Ab≦Ac≦Adとしたときに
① (Aa+Ab)^2+(Ac+Ad)^2
② (Aa+Ac)^2+(Ab+Ad)^2
③ (Aa+Ad)^2+(Ab+Ac)^2
の3通りが有る。①-③と②-③の不等式評価をするとこの3つの組み合わせで③がもっともアンバランス度が低い組み合わせとなる。
これをすべてのペアについて検討して、すべての2ペアを③のように組み替えると、一番値の小さいのと、一番大きいもののペア、2番目に小さいのと、2番めに大きいもののペアというような組み合わせが最適となる。
で、あとはN-Mのペアの選び方だが、配列Aにおいて右側にソロが固まるように、ペアのやつらは左側に固まるようにするのが一番値が小さくなる。（これはほぼ自明でいいと思うが、ちゃんとやるなら一つのペアと一つのソロを見て、ソロを一番大きなやつに割り振ると一番アンバランス度が減るのを確認する）
なので最適解は左から1と2N-2M番目、2と2N-2M-1番目・・・N-MとN-M+1番目のペアと、2M-2M+1、2M-2M+2・・・Nのソロをそれぞれ二乗したものが答え。
これ直感で多分そういう組み合わせが一番小さいとはおもうけれど、きっちり証明するのは絶対に灰diffじゃないと思う
