AtCoder ABC 025 C - 双子と○×ゲーム (試験管青色)

ゲーム探索 + bit DP。やや実装重たい。

• 問題へのリンク

問題概要

先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。

書き終わったとき、次のように得点を計算する

• および に対して、
  • マス とマス が同じ文字のとき、先手に 点、
  • 異なる文字のとき、後手に 点
• および に対して、
  • マス とマス が同じ文字のとき、先手に 点、
  • 異なる文字のとき、後手に 点

両者ともに自分の得点が最大となるように行動するとき、先手と後手のそれぞれの得点を求めよ。

考えたこと

いわゆる「ゲームを DP で解く」系の問題ですね！

そのタイプの問題にまったく馴染みのない方は、次の記事を読んでみてください。

qiita.com

さて、今回のゲームでは、先手の最終得点と後手の最終得点の和は一定値 ( の総和と の総和の和) になることに着目しましょう。

よって、双方の行動原理は「自分の最終得点と相手の最終得点の差を最大化したい」と表現できます。このようなゲームの構造をゼロサムであると言います。ゼロサムゲームを解くためには、次の再帰関数を用いることが多くあります。

// 盤面の状態が state である状態からスタートして、
// その状態で手番であるプレイヤー視点での相手との得点差の最大値を返す
int dfs(State state) {
    // 終端条件
    if (state が終局である) return (終局に応じた得点);

    // 打てる手をすべて試す
    int res = -INF;
    for (state2  : state から遷移できる局面全て) {
        // dfs(state2) によって、相手視点の得点が得られるので -1 倍する
        res = max(res, -dfs(state2));
    }
    return res;
}

なお、このような形式の再帰関数を用いたゲーム探索は、ミニマックス法や、ネガマックス法などと呼ばれます。

競プロでは、この再帰関数をこのまま実装するだけだと TLE になることが多いです。それは、同一局面を何度も何度も探索し得ることが原因です。

そこで、メモ化しましょう。そうすると、いわゆるメモ化再帰と呼ばれる DP になりますね！

今回の問題

今回の問題では、盤面の状態をサイズ 9 の配列で表現することにしましょう。各マスの値を として、配列の各要素に対応させます。ここでは、

• -1 (何も書かれていない)
• 1 (o が書かれている)
• 0 (x が書かれている)

とします。このとき、ありうる盤面の個数は 通りあり、各盤面に対して最大 9 通りの「次の一手」が考えられるため、計算時間は に比例します。十分間に合います。

また、メモ化再帰もきちんと実施します。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<29;

// 入力
vector<vector<int>> b(2, vector<int>(3)), c(3, vector<int>(2));

// 終局時の手番側の得点から、相手側の得点を引いた値を求める (終局時は手番は後手である)
int score(const vector<int> &board) {
    // マス (i, j) のマス番号
    auto mass = [&](int i, int j) -> int { return i * 3 + j; };
    
    int res = 0;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[mass(i, j)] == board[mass(i+1, j)]) res -= b[i][j];
            else res += b[i][j];
        }
    }
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (board[mass(i, j)] == board[mass(i, j+1)]) res -= c[i][j];
            else res += c[i][j];
        }
    }
    return res;
}

// メモ化再帰 (tesuu: すでに文字の書かれたマスの個数)
map<vector<int>, int> dp;
int dfs(vector<int> &board, int tesuu) {
    if (dp.count(board)) return dp[board];
    
    // 終局条件
    if (tesuu == 9) return dp[board] = score(board);
    
    // 打てる手をすべて試す
    int res = -INF;
    for (int i = 0; i < 9; ++i) {
        if (board[i] != -1) continue;
        
        // tesuu が偶数なら先手 (o を書く)、奇数なら後手 (x を書く)
        board[i] = (tesuu % 2 == 0 ? 1 : 0);
        res = max(res, -dfs(board, tesuu+1));
        board[i] = -1;  // 元に戻す
    }
        
    // メモ化しながら返す
    return dp[board] = res;
}

int main() {
    int sum = 0;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 3; ++j) {
        cin >> b[i][j];
        sum += b[i][j];
    }
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 2; ++j) {
        cin >> c[i][j];
        sum += c[i][j];
    }
    
    // メモ化再帰して、先手と後手の得点差を求める
    vector<int> board(9, -1);
    int diff = dfs(board, 0);
    
    // 得点差から、先手と後手の得点を復元する
    cout << (sum+diff)/2 << endl << (sum-diff)/2 << endl;
}