AtCoder ABC 354 E - Remove Pairs (1D, 水色, 475 点)

ChatGPT が問題文コピペのみで解けたと話題になった！

• 問題へのリンク

問題概要

枚のカードがあり、表には 、裏には が書かれている。

先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカードを選び除去する。先に除去できなくなったほうの負けである。

双方最善を尽くしたとき、どちらが勝つか？

制約

• 

考えたこと

bit DP とゲーム DP の組み合わせ。

• dp[S] ← 集合 で表されるカードが残っているとき、その状態て手番のものが勝てるかどうか

として、この値を求めれば OK。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    
    // メモ化再帰
    vector<int> dp(1 << N, -1);
    auto rec = [&](auto rec, int bit) -> int {
        if (dp[bit] != -1) return dp[bit];
        
        // 終端条件
        if (__builtin_popcount(bit) < 2) return dp[bit] = 0;
        
        // まだ使っていない 2 頂点を試す
        int res = 0;
        for (int x = 0; x < N; ++x) {
            if (!(bit & (1 << x))) continue;
            for (int y = 0; y < N; ++y) {
                if (x == y) continue;
                if (!(bit & (1 << y)))continue;
                if (A[x] != A[y] && B[x] != B[y]) continue;
                
                int nbit = bit ^ (1 << x) ^ (1 << y);
                if (!rec(rec, nbit)) res = 1;
            }
        }
        return dp[bit] = res;
    };
    
    int res = rec(rec, (1 << N) - 1);
    if (res == 1) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}