AtCoder AGC033-BのPythonでの実装例

CompetitiveProgramming Python3 競技プログラミング 動的計画法

AtCoder Grand Contest 033 - AtCoder の B - LRUD Game を嘘解法で通してしまったので、自戒のためにも想定解での実装をまとめておきます。

嘘解法の問題点

コンテスト中に提出した嘘解法：提出 #5267609
この実装では、まず駒を進める方向を一つ決めます。そして、先攻がその方向に駒を進められる時は貪欲的に駒を進め、後攻はその逆に駒を貪欲的に戻します。この操作をシミュレートし、途中で駒が盤の外に落ちるかを上下左右の4方向全てに対して調べます。1方向でも駒が落ちれば NOを、全てで駒が落ちなければ YES を返します。

この実装でもコンテストのテストケースを通すことはできますが、以下のようなケースで間違えます。​

このケースに対して嘘解法を実行すると YES となり、駒は落ちないと判定されます。しかし、実際は駒を落とすことができます。
嘘解法では、各プレイヤーは対戦相手の手に関わらず1方向にしか駒を進めません。すなわち、

  • 先攻が駒を右に進めるときは、後攻は駒を左にしか進めない（後攻が左に進めるときは、先攻は必ず右に進める）
  • 逆に先攻が駒を左に進めるときは、後攻は駒を右にしか進めない（後攻が左に進めないときは、先攻は必ず左に進める）

しかし、このケースにおいて、後攻が1ターン目に左に駒を進めた場合、先攻が2ターン目にさらに左に進めることで駒を落とすことができます。
逆に後攻が1ターン目に駒を動かさなかった場合、先攻が3, 4ターン目で右に進めることでやはり駒を落とすことができます。

このように、嘘解法では相手の手に応じて最適な手を選ぶことができません。

想定解

公式解説

想定解は 動的計画法 (DP) を利用します。
各プレイヤーの操作を後ろから順番に見ていき、駒が落下しない範囲を更新していきます。最後まで更新し、初期の駒の位置がこの範囲に入っているかを調べます。以下、この範囲を安全範囲と呼びます。

Python3 での実装例

公式解説では、行と列が独立して動くため別々に更新するように書いてありますが、ここではまとめて長方形として扱っています。

11行目： DPテーブルの初期値として、盤全体を安全範囲とします。安全範囲の下位置, 上位置, 左位置, 右位置をそれぞれ d, u, l, r とし、それらをまとめた tuple でDPテーブルを更新します。
16 - 23行目： 操作の後ろから見ていくため、後攻の操作を先に見ます。後攻は駒を落とさないように、安全範囲を広げます。安全範囲が盤を超えないように注意します。
25 - 32行目： 先攻は安全範囲を狭めます。
34 - 35行目： もし更新の途中でも行または列の安全範囲がなくなった場合は、必ず駒が落下するため更新を打ち切り、 NO を返します。
39 - 43行目： 最後まで更新した安全範囲内に駒の初期位置が含まれているかを確認します。