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 による実装例です。

xxxxxxxxxx
 
# 入力の受け取り
n, m = map(int, input().split())
ax, ay, bx, by = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
​
# 定数の定義
dxy = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 移動の差分
​
​
# (turn: 現在のターン数; ax, ay: Aliceの座標; bx, by: Bobの座標; diff: Aliceのスコア - Bobのスコア)からスタートしたときに、勝つプレイヤーを返す再帰関数。
def f(turn, ax, ay, bx, by, diff):
    # 終了したなら
    if turn == 2 * m:
        if diff > 0:
            return 1
        elif diff == 0:
            return 0
        elif diff < 0:
            return -1
​
    # Aliceのターンなら
    if turn % 2 == 0:
        res = -1
        for i, j in dxy:
            nx = ax + i
            ny = ay + j
            if 0 <= nx < n and 0 <= ny < n and (nx, ny) != (bx, by):
                # 書いてあった数字をメモ
                prv = s[nx][ny]
                # 0 に上書き
                s[nx][ny] = 0
                # 自分にとって最も有利な状態に遷移する。
                res = max(res, f(turn + 1, nx, ny, bx, by, diff + prv))
                # 書いてあった数字を元に戻す。
                s[nx][ny] = prv
    else:
        res = 1
        for i, j in dxy:
            nx = bx + i
            ny = by + j
            if 0 <= nx < n and 0 <= ny < n and (nx, ny) != (ax, ay):
                # 書いてあった数字をメモ
                prv = s[nx][ny]
                # 0 に上書き
                s[nx][ny] = 0
                # 自分にとって最も有利な状態に遷移する。
                res = min(res, f(turn + 1, ax, ay, nx, ny, diff - prv))
                # 書いてあった数字を元に戻す。
                s[nx][ny] = prv
    return res
​
​
# 座標の値は0_indexに直す。
ans = f(0, ax - 1, ay - 1, bx - 1, by - 1, 0)
if ans == 1:
    print("Alice")
elif ans == 0:
    print("Draw")
elif ans == -1:
    print("Bob")
​