左右から見て、スワップする場所をN通り試せるのだろうと思ったけど、それ以上詰めることが出来なかった。
気づき
- スワップする場所を全通り試す
- 石を減らす操作は貪欲に決まる
- 左右から操作結果を記録する
数列に対して、なんらかの操作をした結果、変更した場所しか影響がないという問題はよくあって、これもその手の類問。
（よくあるのは、累積和をとっておいたり、左右から結果を持っておくなどがある。）
まず、
1. 操作をした結果、石は減るだけで、増えることはない。
1より、（左端）の石を取り除くには、
である必要があり、石を取り除いた結果、
、
となるし、
のときは不適となる。
同様にを取り除くとき、
が必要であり……と、左端から順番に処理していくことになる。
さらに同じことが右端から操作するときにも言える。
以上より、
2. 左右から条件を満たす限り操作をおこない、途中で操作が出来ない場合、石をすべて取り除くことはできないと言って良い。また操作が可能であればその位置までは石を0に出来ている。
左からの操作結果を記録した配列をL、右からの操作を記録した配列をRとする。（任意のインデックス（の手前）まで操作したときに、そのインデックスに残っている石の数を記録しておく）
と
をスワップしたときに何が起きるかを考える。
このとき、左からみていってまではスワップ前と同じように操作できるので、影響はない。
同じように右から見ていってまでは影響がない。
よって、
3. または
までの時点で操作が出来ない場合は不適となる。
よって
4. と
をスワップするときは、
の4つを実際にシミュレーションして判定すればよい。
（は左からみてLを利用する。
は右から見てRを利用する）
左右から操作をしたとき、全ての石を取り除くことができる条件は、ある位置、
にたいして、
5. かつ
、
となる。
2.より
、
までに操作が不適になるのであれば当然不適。
そしてインデックス、
まで操作ができるのであれば、最後は隣り合うふたつに同数の石があり、それらを取り除くことで全ての石を取り除くことができる。
実装上のコツ
添字の扱いで混乱するので、累積和をとるときのように、L、Rの最初は0を追加しておくとよい。
L、Rを計算するときに、のときはそのまま
として、マイナスにしてしまってよい。その時点で操作は不適となるので、それ以降は「-1」としておく。
こうしておくとマイナスなら不適だったとして判定できる。
この方法でAC。
