AtCoder ABC 136 E - Max GCD - なにかの記録

問題概要

長さ $N$ の整数列 $A_1 ... A_N$ が与えられる。次の操作を $0$ 回以上 $K$ 回以下行うことができる。

$i≠j$ なる $1$ 以上 $N$ 以下の $2$ つの整数 $i,j$ を選び、 $A_i$ に $1$ を足し、 $A_j$ に $-1$ を足す。この操作の後いずれかの要素が負になってもよい。

操作後の $A$ の全ての要素を割り切る正の整数として考えられる値の最大値を求めよ。

制約

$2≤N≤500$
$1≤A_i≤10^ 6$
$0≤K≤10^ 9$

解説/考察

ステップ1

答えを $z$ 、各 $A_i$ に対して変化させる値を $x_i$ とおくと、

$(A_i+x_i)\equiv 0 \,(mod \,z)$

です。よって

$\sum _ {i=1}^N (A_i+x_i) \equiv 0 \,(mod \,z)$

が成り立ちます。またこのとき、問題文より

$\sum _ {i=1}^N (x_i) = 0$

なので、

$\sum _ {i=1}^N (A_i) \equiv 0 \,(mod \,z)$

と変形できます。よって、答え $z$ は $A$ の総和の約数であることが分かります。

ステップ2

次に、答えの候補を $d$ としたときに、 $K$ 回以内の操作で整数列 $A$ の要素を $d$ の倍数にすることができるのか判定する方法を考えます。
各 $A_i$ について、

$A_i \, mod \,\, d$ を引く(「-方向」)
$d-(A_i \, mod \,\, d)$ を足す(「+方向」)

ことによって $d$ の倍数にすることができます。 $S$ = (「-方向」の量) - (「+方向」の量)とするとき、 $S=0$ となっている必要があります。
まず最初に、 $A$ の全ての要素を「-方向」に設定してみると、

$S_0 = \sum _ {i=1}^N (A_i \, mod \,\, d)$

です。また、これは $d$ の倍数となることが $A$ の総和が $d$ の倍数であることからわかります。
それでは、ここから1つの要素を「+方向」に変えてみます。このとき、 $S$ の変化量は

$-(A_i \, mod \,\, d)-(d-(A_i\,mod\,\,d)) = -d$

となります。よって、 $S_0/d$ 個だけ「+方向」に設定しなおせばよいことがわかります。操作回数は「+方向」に設定しなおした後に残った「-方向」の量です。どの要素を設定しなおしても $S$ の変化量は $-d$ なので、 $S_0$ から、 $\lbrace A_i \, mod \,\, d \rbrace$ のうち大きい方から $S_0/d$ 個の和を引いた値が操作回数の最小値となります。これによって求まった値が $K$ 以内ならば、 $A$ の要素を $d$ の倍数にすることができます。この判定方法をステップ1で挙げた答えの候補のうち大きい方から適用していくことで答えが求まります。

この記事に沿ったソースコードの例です。

思考の流れ

とりあえず文字でおいて式化してみる。

これはあらゆる問題で言えることですが、未知数を一つの文字で置いて、式の最終的な状態、最初の状態、条件式を書き出してみると重要なことが見えてくることが多いです。この問題で言うと、最初の変化量を $x_i$ と置くことで、最後の状態 $A_i+x_i$ の式と条件式から、関係性を見出すことができます。

答えは $A$ の総和の約数で、約数の個数はあまり大きくならない(参考)ので、列挙して一つずつチェックしていけば良い。判定方法を考える。
$A_i$ を $d$ の倍数にしたいとき、 $A_i\,mod \,\,d$ だけ引く、又は $d-(A_i\,mod \,\,d)$ を足せばよいことがわかり、全体でこれをうまく調整することで「引く量」=「足す量」にしたい。
「引く量」と「足す量」の差を考えれば良さそう。式変形(あるいは実験)をすると、差が $d$ の倍数かつ、要素を一つ変えるごとに常に変化量が $d$ であることから、答えにたどり着く。

感想

コンテスト中、ステップ1を思いついたときは、これがこの問題の本質だと思っていましたが、どちらかというとステップ2の判定フェーズの方が骨が折れます。しかしステップ1に気付かなければ何も始まらなく、非常に考察力が試される問題だと思いました。