Number Addtion Game

2 secs 1024 MB

解法の解説

この問題は、 $N \times N$ のグリッド上で、両プレイヤーが交互に最適な動きをするゲームをシミュレーションし、勝者を判定するというものです。制約条件から、全ての可能な移動を探索することが可能なため、再帰的にシミュレーションを行う深さ優先探索（DFS）で解くことができます。

再帰による全探索
すべての状態において、Alice と Bob のどちらのターンであっても、それぞれの駒が移動できる場所を探索し、ゲームの終了条件に至るまでの全ての可能なパスをシミュレーションします。再帰関数 f を用いることで、現在の盤面状況から最適な手を逐次計算します。
勝利条件のチェック
各ターンのスコア差を引数として持ち、最終ターン後（ $M \times 2$ ターン経過後）にスコア差がどうなっているかを基に、勝者を判定します。

このゲームでは、再帰関数 f を用いて、Alice と Bob が互いに最適な選択を行い、最終的な勝敗を導きます。各プレイヤーはすべての手を読み切り、その結果に基づいて最良の行動を選択します。
max と min の役割
f 関数内では、ターンが Alice の場合、彼女にとって最も有利な選択肢を取るために max 関数を使います。逆に、Bob のターンでは、彼にとって最も有利な選択肢を取るために min 関数を使います。

ここで重要なのは、「結果として返ってくる値が何を意味するか」です。f 関数は最終的な勝敗を示す 1（Alice の勝利）、0（引き分け）、-1（Bob の勝利）を返すので、これを基にどの行動を選ぶかが決まります。
- Alice のターンでは、max を使って次の状態の中から最も良い結果（値が大きい、つまり Alice が勝つ結果）になるものを選びます。
- Bob のターンでは、min を使って次の状態の中から最も良い結果（値が小さい、つまり Bob が勝つ結果）になるものを選びます。

このアルゴリズムの計算量を評価すると、以下のようになります。

状態数の見積もり
各プレイヤーは $N \times N$ の盤面上で自分の駒を動かすため、各ターンごとに最大で 4 方向に動けると仮定できます。
- Alice のターンには最大で 4 つの移動候補があり、それぞれの状態で次の Bob のターンも同様に 4 つの移動候補があります。
- $2M$ ターン分の探索があるため、状態数は約 $4^{2M}$ です。
各状態ごとの計算量
各状態では、グリッドの書き換えを行うのみであり、 $O(1)$ で行えます。

よって、問題全体の計算量は、入力に関する処理の $O(N^2)$ 、答える求める処理の $O(4^{2M})$ を合わせて $O(N^2 + 4^{2M})$ であり、十分高速です。

以下は Python による実装例です。