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

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

• 問題へのリンク

問題概要

はじめ、高橋君は整数 の書かれた 枚のカードを持っていて、青木君は整数 の書かれた 枚のカードを持っていて、場には整数 の書かれた 枚のカードがある。

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

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

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

制約

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

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

といったことである。今回は、 として、高々 通りの局面がある（各カードにつき、「高橋君の手札」「青木君の手札」「場」のどこにあるかで 3 通りあるため）。 なので、現実的な数だと言える。

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

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

qiita.com

計算量は となる（局面数が 個、遷移が 通りあるため）。

コード

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

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

の組をキーとする（メモ化する際に、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;
}