Game in Momotetsu World [マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201） D]

https://atcoder.jp/contests/abc201/tasks/abc201_d

前提知識

• ミニマックス法

解説

https://atcoder.jp/contests/abc201/submissions/22636331

今回のゲーム問題はミニマックス法を知らないとだいぶ解くのが厳しい。
DPといえばDPではあるが、このやり方をDPから導くのはなかなか難しい。

DPについて

以下のDPを作っていく。

dp[y][x] := 駒が(x,y)にあるときの「高橋君の点数-青木君の点数」の最適値
高橋君の手番の時はこの値を最大化するように動くし、青木君の手番の時はこの値を最小化するように動く。
このように手番によって利得を最小化、最大化するようにしてDPっぽく計算するやり方がミニマックス法。

座標が分かればx+yによってどちらの手番かどうかが分かる。
(x+y)%2=0なら高橋君の手番だし、(x+y)%2=1なら青木君の手番である。
どっちのプレイヤーの手番であるかを考えて、最小化・最大化の遷移を行おう。
あとは、高橋君の操作の場合は利得が増えるが、青木君の場合は-青木君の点数なので利得は減らすことになる。
最終的にdp[0][0]を見れば、勝敗が分かる。

メモ化再帰

自分は実装では、このDPをメモ化再帰で実装している。
特に意味はないので、ループで実装しても問題ない。
ゲーム系は癖でメモ化再帰を使ってしまうだけ。

int H, W;
string A[2020];
//---------------------------------------------------------------------------------------------------
bool vis[2020][2020];
int memo[2020][2020];
int dp(int x, int y) {
    if (vis[y][x]) return memo[y][x];
    vis[y][x] = true;

    int turn = (x + y) % 2;

    if (x == W - 1 && y == H - 1) return memo[y][x] = 0;

    if (turn == 0) {
        // Takahashi
        memo[y][x] = -inf;
        if (y < H - 1) chmax(memo[y][x], dp(x, y + 1) + (A[y + 1][x] == '+' ? 1 : -1));
        if (x < W - 1) chmax(memo[y][x], dp(x + 1, y) + (A[y][x + 1] == '+' ? 1 : -1));
        return memo[y][x];
    }
    else {
        // Aoki
        memo[y][x] = inf;
        if (y < H - 1) chmin(memo[y][x], dp(x, y + 1) - (A[y + 1][x] == '+' ? 1 : -1));
        if (x < W - 1) chmin(memo[y][x], dp(x + 1, y) - (A[y][x + 1] == '+' ? 1 : -1));
        return memo[y][x];
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];

    int opt = dp(0, 0);

    if (0 < opt) cout << "Takahashi" << endl;
    else if (opt == 0) cout << "Draw" << endl;
    else cout << "Aoki" << endl;
}