AGC 033 B - LRUD Game

• 問題
• AC

明らかに水平と垂直をわけて考えてよいので、１次元区間の上を左右に動いて脱出するかしないかを判定する問題になる。これだったら難しい考え方はいらないはず……と思ったのだが、そこから正解にたどりつくのに難航した。100分かけてAC。

入力例2を例に取る。長さ3の区間で初期位置が真ん中([ ][s][ ])の場合に、そこから右へ脱出できるかどうかを考える。例に上がっている操作列を検討する:

• 高橋君: XXRRR
• 青木君: LLXXX

（Xは上下の移動とする）

まず、右への累積移動量（=高橋君のRから青木君のLを引いたもの）だけで判定することはできない。この方針を例に適用すると、どの時点を取っても高橋君の累積移動量は+1を超えていないので、右には脱出できないことになってしまうが、実際には青木君は1回しか左に移動できないので、高橋君はRを3回選んで右に脱出できる。

次に、貪欲法を考える。高橋君ができるだけ右に行こうとし、青木君ができるだけ左に行こうとしたときに右に脱出するかどうかを判定する。しかし、これも（同じ区間で）次の操作列の時にうまくいっていない:

• 高橋君: XRRL
• 青木君: LXXX

青木君がLを選べば高橋君は確かに右には脱出できなくなるが、代わりに左に脱出可能になってしまう。逆に、青木君がLを選ばなければ高橋君はRを2回選んで右に脱出できる。この例に気づいたので、前から判定する方針は難しそうと感じた。¹

そこで、後ろからの判定を試みる。やはり１次元区間$\{1, 2, ..., H\}$上で考える。 $i$ターン目の開始時にマス$x$にいるとして（高橋君がうまく操作すればいずれ）右に脱出可能だとするとき、マス$x+1$にいても右に脱出可能であるし、左に脱出可能だとするとマス$x-1$も左に脱出可能であることに注目すると、安全なマスは常に連続した区間で表されることがわかる。つまり、$x < l_i$なら左に脱出可能で、$r_i < x$なら右に脱出可能で、$l_i \le x \le r_i$なら安全であるような$l_i$, $r_i$が存在する。これを具体的に求めたい。

最初からわかっているのは、$l_{N+1} := 1$, $r_{N+1} := H$、つまり$N+1$ターン目の開始時（＝ゲーム終了時）には$\{1, 2, ..., H\}$のどこにいても安全ということだけである。ここから青木君の$N$番目の操作→高橋君の$N$番目の操作→青木君の$N-1$番目の操作→……と逆順に操作をたどって1足したり引いたりしながら$l_i$, $r_i$を求めていく。途中で$l_i > r_i$となって安全なマスがなくなってしまったり、初期位置$s_x$が安全な区間$[l_1, r_1]$に入っていなかったりする場合はNO、それ以外はYESになる。

解いているときは気づかなかったが、これは自明なDPの高速化からも導ける。$i$ターン目の開始時にマス$j$にいるときに安全かどうかを$dp[i][j]$で持つと時間も空間も足りないが、安全/危険の境界だけわかれば良いことを利用すると${\mathcal O}(n)$に落ちるわけだ。（参考: http://kyopro.hateblo.jp/entry/2019/05/06/002102 ）

一般にbool値を求めるDPは無駄があることが多く、同じ計算量でもっと多くのことを知ることができます。（プログラミングコンテストチャレンジブック 第2版、p. 63）

蟻本のメタ方針を思い出したら、もっと早く正しい方針が得られたかもしれない。

---

1. コンテスト後に振り返ると自明に見えるけれど、コンテスト中はここまでたどり着くのに50分くらいかかっている。 ↩︎