問題
個の箱が円環状に並んでおり、番目の箱には個の石が入っている。「を一つ定めからまでの各に対して番目の箱から石をちょうど個取り除く」という操作を繰り返したとき全ての石を取り除くことは可能か判定せよ。
解答
1時間考えてもわからなかったので解説PDFを読んだ。以下はほとんどその写し。
まず1回の操作で取り除かれる石の個数はなので、必要な操作回数がわかる。そしての変化を考えると、各操作で一つのについてが足され、その他はが引かれる。前処理として事前に全てのに対してを引いておけば、どれか一つにが足されるという変化だけになる。
最終的にはとなればいいので、つまり操作をする前では「 かつはで割り切れる」となっていれば良い。
思考過程
最初に思いついたのが「最大値を見つけてそこをとする」ことを繰り返すという解法であり、これを提出してTLE。計算量の見積もりが全然ダメで、これでいけるのではとか思ってしまった。その後しばらく最大の位置をなんとか上手く発見できるのではないかとか考えていたが上手くいかず。
その後はいくらかのについて二回様々なを選んだ時の配列の様子がどうなるかを確認して法則性を見つけようとする。しかしよくわからない。
30分くらいして隣との差分に注目するということは思いついた。の関係から解の候補が一つに定まって、他はそれを検証するだけで良いのでは? という考えに至るが、一つに定まることはないし定まっても多分検証にかかるのでダメだろう。これを考えているうちに1時間経ってしまった。
反省
まず「必要な操作回数がわかる」という考え方に至っていなかったのはひどかった。最後の方で少し一回で取ることになる石の数ということについて考えていたが、こういう荒っぽい条件の絞り込みというのは早めに思いつくべきだと思う。
そして最大値を発見してそこをとする方法では、発見がでできたところで計算量は間に合わないだろう。こういった繰り返しによる解法は大抵の場合間に合わない作りになっている気がする。ここを見切れず結構な時間を費やしてしまったのは良くない。
詰まったときに実験しに行ったこと自体は悪くないと思う。実験にかけた時間もそこまで長くはなくて、これくらいが適量だろう。
差分に注目したとは書いたが実際のところはなどのまだ二つの具体的な値がどうなるかについて考えていて、配列を全て差分のものに置き換えて問題を変更するというところまで至らなかった。操作が差分に対してどうなるか、差分は最終的にどうなっていればいいか、などから正しい解法を思いついていければ良いと思う。