☆ゲーム(エクサウィーズ2019C - Snuke the Wizard)
考察過程
いちいち更新してると2乗かかってしまう
一回の操作による移動を手早くできる方法がないかな?
最終的に端っこから出てしまうか出てしまわないかが大事。
→最終的に端っこにあるゴーレムがあるとして、そうなってしまうゴーレムの初期位置を逆算していけば良い
0番目とN+1番目にマスがあると仮定して、最終的にその２つのマスにいるゴーレムのみを考える。
Q回目の操作（最後の操作）について、
- d_Q=Lかつs_1=t_Qなら、1番目のマスに0番目のゴーレムを動かす。
- d_Q=Rかつs_N=t_Qなら、N番目のマスにN+1番目のゴーレムを動かす。
- どちらでもなければ、Q番目の操作をする前でも0,N+1番目のマスに存在していた場合しか最終的に外に出る場合はないので、そのままにする。
このようにして操作を繰り返し、1回目の操作についてまで逆ざんしたら、ゴーレムがたどり着けないマスの個数を求めれば良い。☆なぜなら、左端に到達するもっとも右のゴーレムより左のゴーレムは全て左端に到着するからである。
計算量はQ
解法
と思ったけど、逆斬で求めたゴーレムの左端と右端にゴーレムがそれまでの操作で存在しているかわからないからダメじゃん…
正解は左端と右端になるゴーレムを二分探索するでした…
コード
いつか書く
