AtCoder Beginner Contest 136 E - Max GCD

お題箱より。

E - Max GCD

解法の正当性について知りたいというリクエストだったので、そこをメインに解説します。

解法

操作によって全ての要素の合計は変わりません。そして操作後の $A$ の全要素が値 $d$ の倍数であるならば、 $A$ の合計値も $d$ の倍数であるはずです。

このことから答えの候補となるのは、与えられた $A$ の合計値の約数に絞られることが分かります。そのような $d$ を1つずつ試していくことにしましょう。

ある $d$ について試す時に、各 $A_{i}$ を $d$ の倍数にするための最小操作回数を考えます。このとき、 $A_{i}$ を減らす量の合計と増やす量の合計は「つり合っている」必要があります。

まずは $A_{i}$ を全て $A_{i} \bmod d$ に置き換えます。この上で、 $A_{i}$ の目標値として $0$ と $d$ のみ考えれば良いことをまず示します。

操作後の $A_{i}$ として、もし $-d$ 以下の値と $2d$ 以上の値が両方とも存在している場合は、はみ出ている部分を相殺することでより良い解に変更できるので最適ではないです。

また、例えば $-d$ 以下の値だけが存在している場合は、 $d$ を目標値としている要素を適当に選んで以下のように相殺することで、操作回数を変えずに $-d$ 以下の値をなくすことができます。

f:id:betrue12:20200328134444p:plain

これで $A_{i}$ の目標値として $0$ と $d$ のみ考えれば良いことが分かりました。ではこれをどのように割り当てれば良いかというと、 $A_{i}$ （元は $A_{i} \bmod d$ ）の小さい方から $0$ を、大きい方から $d$ を目標値とするように割り当てて、プラスの操作分とマイナスの操作分がぴったり一致するところで区切るのが最適になります。証明しましょう。

まずこのように「ぴったり」区切れることは、 $A_{i}$ の合計が $d$ の倍数であることから分かります。具体的に $A_{i}$ の合計を $kd$ とすると、 $d$ が目標値に割り当てられるのは大きい方からちょうど $k$ 要素になります。以下の図のようにマイナス操作分の値をプラス操作のところに詰め込むとイメージすると、ちょうど収まることが分かります。