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

• 問題
• AC

最初、位置ではなくゴーレムにアルファベットが振られている問題と読み間違えてしまい、すべて実装し終わってサンプルでテストするまで気づかなかった（30分ロス）。誤読することがあるのは仕方ないけれど、最初にサンプルをシミュレーションすれば気づけたはず。

考察は基本原則に従った: AとBを同時に処理しなければならない場合はまず、Aだけで良いとしたら？と考える。今回の場合、LとRが混在することで逆に問題が簡単になるというのは明らかにありえないので、まず片方だけの場合について解けなければどうしようもないと思える。

呪文がRしかない場合について、サンプルのAABCBDBAを例にとって考える。初期位置$i$のゴーレムが（右に）消滅するのはそれぞれ呪文の部分列に

1. A, A, B, C, B, D, B, A
2. A, B, C, B, D, B, A
3. B, C, B, D, B, A
4. C, B, D, B, A
5. B, D, B, A
6. D, B, A
7. B, A
8. A

が含まれている場合だが、これらを素朴に１つずつチェックしていくと${\mathcal O}(QN)$になってしまう。しかし、例えば呪文の部分列にB, D, B, Aが含まれれば当然D, B, Aも含まれるので二分探索して境界を探せば${\mathcal O}(Q \log N)$ですむ。

こうなると、呪文にLとRが混在する場合も二分探索でできるのでは？と考えたくなるが、できる。ゴーレムが他のゴーレムを追い越すことはないので、初期位置$i$のゴーレムが右に消えるなら初期位置$i+1$のゴーレムも消えるし、左に消えれば$i-1$のゴーレムも左に消える。したがって、$i \le p$なる$i$がすべて左に消滅するような最大の$p$と、$q \le i$なる$i$がすべて右に消滅するような最小の$q$を二分探索で求めると、答えは$\max (0, q - p - 1)$である。

いきなり太字の核心部分に気づけるほうが頭いい感じだけど、気づかなくても解けるようになったのは進歩だと思うことにする。