AtCoder Grand Contest 010 B - Boxes

問題

 N個の箱が円環状に並んでおり、i番目の箱にはA_{i}個の石が入っている。「iを一つ定め1からNまでの各jに対してi+j番目の箱から石をちょうどj個取り除く」という操作を繰り返したとき全ての石を取り除くことは可能か判定せよ。

解答

 1時間考えてもわからなかったので解説PDFを読んだ。以下はほとんどその写し。

 まず1回の操作で取り除かれる石の個数は \frac{n(n+1)}{2}なので、必要な操作回数kがわかる。そしてd_i = A_{i+1} - A_{i}の変化を考えると、各操作で一つのiについて(N - 1)が足され、その他は1が引かれる。前処理として事前に全てのd_iに対してkを引いておけば、どれか一つにNが足されるという変化だけになる。

 最終的には\forall i, d_i = 0となればいいので、つまり操作をする前では「 \forall i, d_i \le 0 かつ d_{i}Nで割り切れる」となっていれば良い。

思考過程

 最初に思いついたのが「最大値を見つけてそこをiとする」ことを繰り返すという解法であり、これを提出してTLE。計算量の見積もりが全然ダメで、これでいけるのではとか思ってしまった。その後しばらく最大の位置をなんとか上手く発見できるのではないかとか考えていたが上手くいかず。

 その後はいくらかのNについて二回様々なiを選んだ時の配列の様子がどうなるかを確認して法則性を見つけようとする。しかしよくわからない。

 30分くらいして隣との差分に注目するということは思いついた。A_0とA_1の関係から解の候補が一つに定まって、他はそれを検証するだけで良いのでは? という考えに至るが、一つに定まることはないし定まっても多分検証に O(N^2)かかるのでダメだろう。これを考えているうちに1時間経ってしまった。

反省

 まず「必要な操作回数kがわかる」という考え方に至っていなかったのはひどかった。最後の方で少し一回で取ることになる石の数ということについて考えていたが、こういう荒っぽい条件の絞り込みというのは早めに思いつくべきだと思う。

 そして最大値を発見してそこをiとする方法では、発見がO(1)でできたところで計算量は間に合わないだろう。こういった繰り返しによる解法は大抵の場合間に合わない作りになっている気がする。ここを見切れず結構な時間を費やしてしまったのは良くない。

 詰まったときに実験しに行ったこと自体は悪くないと思う。実験にかけた時間もそこまで長くはなくて、これくらいが適量だろう。

 差分に注目したとは書いたが実際のところはA_0とA_1などのまだ二つの具体的な値がどうなるかについて考えていて、配列を全て差分のものに置き換えて問題を変更するというところまで至らなかった。操作が差分に対してどうなるか、差分は最終的にどうなっていればいいか、などから正しい解法を思いついていければ良いと思う。