エクサウィザーズ2019 C. Snuke the Wizard
問題
N個のマスが並んでおり、各マスには1体のゴーレムと1文字が書かれている。
ここで、呪文を唱えると、ある文字の書かれたマスにいるすべてのゴーレムを右か左に1マス移動させることができる。
マスの外側に移動させられたゴーレムは消滅する。
Q回の呪文が与えられるので、最終的にマスに残っているゴーレムの数を答えよ。
制約
- 1 <= N, Q <= 2*10^5
- 文字は英大文字のみ
解法
あるマスxにあるゴーレムが左側から消滅する場合、マスx-1にあるゴーレムも(通過するはずなので)必ず左側から消滅する。(右側も同様)
なので、消滅するか否かを二分探索で位置を求めればよい。
反省
本番中は、両端から消滅ゴーレムは連続するのは気づいたけど、呪文を逆順にして消滅する範囲がどこまでか？を見つける様な方法でアプローチしてしまった。
これの場合、
2 2 AB A R A L
のケースでは、1つ目のマスのゴーレムが落ちる様な計算をしてしまうが、そのゴーレムは呪文1で2つ目のマスに移動していてゴーレムがないので、消滅するゴーレムはない。
なので、消滅しない範囲に移動したかどうかも同様な感じで求めればいいか？と提出したけど、両端からの範囲が重なるようなケース
2 3 AB B R A R A L
など、いろいろ嘘だった。
