けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 380 F - Exchange Game (2D, 青色, 500 点)

場からカードを手札に入れない方が良い場合があるの、すごい! あと、局面状態を数値情報にエンコードするかを迷ったけど、エンコードしなくても通った。

問題概要

はじめ、高橋君は整数  A_{1}, \dots, A_{N} の書かれた  N 枚のカードを持っていて、青木君は整数  B_{1}, \dots, B_{M} の書かれた  M 枚のカードを持っていて、場には整数  C_{1}, \dots, C_{L} の書かれた  L 枚のカードがある。

高橋君からはじめて、交互に次の操作を繰り返す

  1. 手札のカードを 1 枚選んで場に出す(その整数値を  a とする)
  2. 場のカードから 0 枚または 1 枚のカードを選び、そのカードの整数値が  a 未満であるならば、手札に入れる( a 以上ならば何もしない)

先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか?

制約

ゲームの勝敗を求める問題では「まず DP できないか?」を考えると良いと思う。気にすべきポイントは

  • 考えられる局面は何通りあるのか?
  • 有限回数で終了するか? (局面がループすることはないか?)

といったことである。今回は、 S = L + M + N として、高々  3^{S} 通りの局面がある(各カードにつき、「高橋君の手札」「青木君の手札」「場」のどこにあるかで 3 通りあるため)。 S \le 12 なので、現実的な数だと言える。

また、ゲームが進むにつれて「お互いの手持ちのカードの枚数、または、場のカードの整数の総和」の値が単調減少であるから、局面がループすることはない。

よって、いつものゲーム DP をすればよい。ゲーム DP のやり方は、たとえば次の記事などに書いた。

qiita.com

計算量は  O(3^{S}S^{2}) となる(局面数が  O(3^{S}) 個、遷移が  O(N^{2}) 通りあるため)。

コード

局面を整数値にエンコードするか悩んだけど、ここでは

  • 高橋君の手持ちのカードの整数値
  • 青木君の手持ちのカードの整数値
  • 場のカードの整数値

の組をキーとする(メモ化する際に、map<array<vector<int>, 3>, bool> を使う)ので通った。

#include <bits/stdc++.h>
using namespace std;
using Node = array<vector<int>, 3>;  // 盤面の状態

int main() {
    int N, M, L;
    cin >> N >> M >> L;
    vector<int> A(N), B(M), C(L);  
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    for (int i = 0; i < L; i++) cin >> C[i];

    // 自分の手札が x, 相手の手札が y, 場のカードが z であるときの勝敗:dp[{x, y, z}] を求める
    map<Node, bool> dp;
    auto rec = [&](auto rec, Node v) -> bool {
        // 終了状態かどうかの判定
        if (v[0].empty()) return false;

        // メモ化再帰の処理
        if (dp.count(v)) return dp[v];

        // 場にカードを出す
        bool res = false;
        for (int i = 0; i < v[0].size(); i++) {
            int val = v[0][i];
            vector<int> nx = v[0], ny = v[1], nz = v[2];
            nz.push_back(val);
            nx.erase(nx.begin() + i);
            sort(nz.begin(), nz.end());

            // 場にあるカードを取らない場合
            if (!rec(rec, Node({ny, nx, nz}))) res = true;

            // 場にあるカードを順に試す
            for (int j = 0; j < nz.size(); j++) {
                if (nz[j] >= val) break;
                vector<int> nx2 = nx, ny2 = ny, nz2 = nz;
                nx2.push_back(nz[j]);
                nz2.erase(nz2.begin() + j);
                sort(nx2.begin(), nx2.end());
                if (!rec(rec, Node({ny2, nx2, nz2}))) res = true;
            }
        }
        return dp[v] = res;
    };

    cout << (rec(rec, Node({A, B, C})) ? "Takahashi" : "Aoki") << endl;
}