エクサウィザーズ 2019 C - Snuke the Wizard

消滅していないゴーレムを数えるのではなく消滅するゴーレムを数えよう、というところまでは思い至ったのだけど結局解けず。解説見て一発で理解出来て悔しかった。

とうことで、どんな事を検討していたら解けたか考えてみる

1クエリで最悪10**5箇所に更新がかかるので、全てをシミュレートするのは無理。よって、各場所に何体ゴーレムが残るかを計算するのではなく、残るゴーレムの総数を直接計算するはず。
残るゴーレムではなく、落ちるゴーレム(補集合)を考える。
例えば左から落ちるやつ/落ちないやつを列挙してみる。
系列が途中で切り替わる(今回なら左から落ちるやつ、落ちないやつの切り替わり)なら、切り替わり地点を探して数を計算する。
切り替わって元に戻らないなら二分探索で探せる。

こんなところか。今回落ちるやつは手でシミュレーションしてたけど落ちないやつの判定まではしていなくて、それで途中で落ちる/落ちないが切り替わって戻らないというのが気付けなかった感ある。

二分探索で切り替わるところを探したけど、呪文を後ろから見ていくという方法で切り替わる部分を探すことができる。

二分探索だとシミュレートにO(Q)、切り替わる点を探すのにO(log(N))かかるが、こっちだとO(Q)だけで計算できて早い。実際pythonだと二分探索だと1800msくらいかかってギリギリだったが後ろから見る方式だと500msくらいだった。

いずれにしても落ちる/落ちないが途中で切り替わることに気付けないとだめ