マイナビプログラミングコンテスト2021 D - Game in Momotetsu World【Python解答例】

マイナビプログラミングコンテスト2021(AtCoder Beginner Contest201)のD問題についてPythonの解答例を記事にしていきます。
Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） - AtCoder

AtCoder Beginner Contest201 D - Game in Momotetsu World

D - Game in Momotetsu World

問題文

H 行 W 列のマス目があり、各マスは青マスまたは赤マスのどちらかです。上から i 番目、左から j 番目のマスは、Ai,j が + なら青マスであり、- なら赤マスです。
最初、このマス目の一番左上のマスに一つ駒が置かれていて、高橋君と青木君はこの駒を使ってゲームをします。
2 人の得点は最初 0 点ずつです。
2 人は、高橋君から始めて交互に次の操作をします。

・駒を一つ右または一つ下のマスに動かす。ただし、駒がマス目の外に出るような動かし方はできない。動かした人は、駒の移動後のマスが青マスなら 1 点を得て、赤マスなら 1 点を失う。

どちらかが操作できなくなった時点でゲームは終了します。ゲームの結果は、終了時の 2 人の得点が異なるならば得点の大きい方が勝ち、同じならば引き分けとなります。
両者とも自分の勝敗が最適になるように行動したとき、ゲームの結果を求めてください。

制約

・1≤H,W≤2000
・Ai,j は + または -

解答例

INF = 1e9

h, w = map(int,input().split())

A = []
for i in range(h):
    array = input()
    A.append(array)

# スコア変動
MAP = []
for i in range(h):
    array1 = []
    for j in range(w):
        a = A[i][j]
        if a == "+":
            array1.append(1)
        else:
            array1.append(-1)
    MAP.append(array1)

# マス(i,j)のときの高橋-青木のスコア
dp = [[0]*2005 for _ in range(2005)]
dp[h][w] = 0

for i in reversed(range(h)):
    for j in reversed(range(w)):
        if i == h-1 and j == w-1:
            continue
        
        k = i + j
        # 高橋くんのターン
        if k % 2 == 0:
            tmp1 = 0
            tmp2 = 0
            # 右へ移動
            if i + 1 < h:
                tmp1 = dp[i+1][j] + MAP[i+1][j]
            else:
                tmp1 = -INF
            # 下へ移動
            if j + 1 < w:
                tmp2 = dp[i][j+1] + MAP[i][j+1]
            else:
                tmp2 = -INF
            dp[i][j] = max(tmp1, tmp2)
        
        # 青木くんのターン
        else:
            tmp1 = 0
            tmp2 = 0
            # 右へ移動
            if i + 1 < h:
                tmp1 = dp[i+1][j] - MAP[i+1][j]
            else:
                tmp1 = INF
            # 下へ移動
            if j + 1 < w:
                tmp2 = dp[i][j+1] - MAP[i][j+1]
            else:
                tmp2 = INF
            dp[i][j] = min(tmp1, tmp2)

ans = dp[0][0]

if ans == 0:
    print("Draw")
elif ans > 0:
    print("Takahashi")
else:
    print("Aoki")

解説

H行W列のマス目があり、」高橋君と青木君が右か下に駒を動かします。
駒の移動先の色によって得点が増減するゲームにおいて、最適な行動を行った場合の勝敗を答える問題です。

公式解説やこちらの記事を参考にさせていただきました。
参考元の記事を読むのが一番だと思いますが、簡単に記事にしたいと思います。

動的計画法DPで解いています。

マス目( i , j ) において、高橋君の得点から青木君の得点を引いた値をdp配列に格納していきます。
ゴール地点を0として、高橋君のターンではdpの値が大きくなるよう、青木君のターンは小さくなるように遷移していきます。

スタート地点のdp配列の値によって誰が勝利できるか判断して出力すればOKでした。

ABC201の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com