解きました
2400点よりは簡単なんじゃないでしょうか...?(これはわかりません)
自分的最難関ポイントは一回見えた性質を捨てるところにありました
解き方
一週間それしか考えないをします(そのおかげでごはんを数回食べそこなって小テストでひどい点をとってサークル活動に支障が出ましたが気にしません)
解法を無理やり生やしてACします
おわり
解法(というより思考の道筋)
実験をするとセルオートマトンみたいであることに気づき、二人とも1であるようなビットが弾丸のように飛んでいくことがわかります。
弾丸の速度は真空中で1で、それ以外の速度の移動物体はなさそうなので弾丸は互いに追い越しません。(実際は物体との相互作用で弾丸は光速を超えて動きますが物体は一度に一つの弾丸とだけ相互作用するので大丈夫であることがわかります。)
なので、後ろの弾丸から独立に 回動かせばいいことがわかります。
弾丸を除いた部分をレールとして、弾丸が通った後にレールがどのようになっているかを考えました。
いっぱい実験すると十分な数の弾丸が通った後のレールは、00が続く真空の中に01だけがある物体(eater)と10 01のようになっている物体(発射装置?)があることがわかります。
真空中を移動するとき弾丸は何事もなく速度1で動きます。
eaterに弾丸が入ると弾丸は消えて、eaterは発射装置になります。
発射装置に弾丸が入ると弾丸は速度2で移動し、発射装置はeaterになります。
なので、非0のところだけを考えると、非0のかたまりひとつあたり確率 くらいで弾丸が消えることがわかり、愚直にしても償却定数個しか見なくてもいいのかな？という気持ちになります。
最初eaterと発射装置を持っておくことにしようかと思ったんですけど、実装が重くなったので同一値の区間を、pair<int, int> : first - 区間の先頭, second - 埋まっている値でsetに入れておくことにしました。
遷移を考えて頑張って実装すると終わりです(AC)
解説見たけどよくわかりませんでした。
以上です。
