エクサウィザーズ 2019 C - Snuke the Wizard
解法
後ろから見ると見通しがよくなるパターンの問題です。
”消滅しないロボットの左端"をとします。これを、
で求めていきます。同様に右端を
とし、最後にその区間に含まれるロボットの数、つまり
を求めれば答えとなります。
左端と右端は、正反対のことを考えればよいので、とりあえず左端、について求めることを考えます。
このとき、一番左、番目のロボットが消滅するためには、すくなくとも
""
という入力が必要です。
同様に考えていくと、
番目のロボットが消滅するためには、すくなくとも
""
という入力があり、かつ
それより後に、
"", "
", ... "
"
の順番でどこかしらにこれらの入力が存在している必要があります。
ということで、この条件をふまえると、番目が消滅するとき、
は必ず消滅するため、初期値
として、呪文を後ろから順番に確認していき、
""
という入力が合った場合にを1増やす、という操作を行っていけば良さそうです。
が、このままだと矛盾するケースがあり、
""
という入力が存在していた場合です。
の定義より、
未満のロボットはすべて消滅するはずですが、上のような入力が出てきた場合、
番目のマスに存在しているロボットは、"
"という入力よりも前に反対方向に進んでしまうため、最終的に消滅することはありません。
逆に、以上のマス目に存在しているロボットも、すくなくとも
番目のマスにしか来れないため、消滅することはありません。
加えて、未満のマス目に存在しているロボットは、"
"
で影響を受けることはないため、結果的に次のような操作をすればよいです。
- "
"の入力が来た場合は
を1減らす
まとめると、初期値をとして、呪文を後ろから見ていき、
"
"の入力が来た場合は
"
という操作を行っていけば、”消滅しないロボットの左端"が求まります。
についてもほぼ同じことを行えば、
が答えになります。
感想
最初見たときは解けなくてDへ逃げたのですが、冷静に考えてみると、後ろからやっていくのがよさそう、となったので実装しました。
""のコーナーケースに気づいたのが提出をしてからで、解法自体はほぼエスパーでした…
証明もふわっとしかできていないので（これで嘘だったらごめんなさい）、ここが今後の課題かと思います！
