AtCoder が提供しているABC（AtCoder Beginner Contest）354 E問題をC++とPythonで解いてみました。ABC354は、2024年5月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Remove Pairs（Difficulty : 1223）
問題の詳細は、リンク先をご覧ください。
bitDPを使ってゲーム問題を解きます。AtCoder Problems による Difficulty は 1223 でした。
解答案
DPを使います。dp[i] は、残っているカードの集合 i のときに、勝つカードの組を選べる場合に 1、どのカードを選んでも負けるもしくはカードが選べない場合に 0 とします。集合 i は、整数と考えて2進数の下位 j bit目が 1 であれば、カード Aj （裏面は Bj）はまだ使われず残っているとします。
残っている文字列の集合 i と、次に選ぶカード j とカード k は、以下を満たす必要があります。
- 集合 i の下位から j bit目と k bit目が 1 になっている（2つのカードが使われずに残っている）。
- カード j とカード k の表同士の数字か裏同士の数字が一致している。
この場合、dp[i から j と k を抜いた集合] が相手の負け（0）になっていれば、カード j とカード k を選ぶことで勝つことができます。逆にどのカードを選んでも勝てなければ、負けとなります。また、カードが選べない場合も負けになります。
集合 i は、値が少ない方から調べていけばよいです（bitDP の考え方です）。初期値は、以下となります。
dp[0]=0、それ以外の初期値は -1 とします。
選べるカードが無ければ、その時点で負けになるためです。
C++ プログラム例（ABC354E）
考察したように dp を更新します。
- すべての j と k の組み合わせに対して、集合 i の下位から j bit目と k bit目が 1 になっていて（19行目）、カード i とカード k の表同士または裏同士が一致していることを確認します（20行目）。
- dp[i から j と k を抜いた集合] が相手の負け（0）になっていれば（21行目）、dp[i] は勝ち（1）になります（22行目）。
以下が、C++プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<int> dp(1 << n, -1);
dp[0] = 0;
for (int i = 1; i < (1 << n); ++i) {
int w_or_l = 0;
for (int j = 0; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if ((((1 << j) & i) != 0)&&(((1 << k) & i) != 0)) {
if (((a[j] == a[k])||(b[j] == b[k]))
&&(dp[i ^ (1 << j) ^ (1 << k)] == 0)) {
w_or_l = 1;
}
}
}
}
dp[i] = w_or_l;
}
if (dp[(1 << n) - 1] != 0) {
cout << "Takahashi" << endl;
} else {
cout << "Aoki" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC354E）
Python版も基本的な考え方は同じです。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 354 E"""
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
dp = [-1] * (1 << n)
dp[0] = 0
for i in range(1, (1 << n)):
w_or_l = 0
for j in range(n):
for k in range(j + 1, n):
if i & (1 << j) != 0 and i & (1 << k) != 0:
if (a[j] == a[k] or b[j] == b[k]) and \
dp[i ^ (1 << j) ^ (1 << k)] == 0:
w_or_l = 1
dp[i] = w_or_l
print("Takahashi" if dp[(1 << n) - 1] != 0 else "Aoki")こちらも「AC」と判定されました。
最後に
前日の記事で、ABC278F問題（解説記事）を紹介しました。問題としては同じ構造でした。似た問題を続けて紹介することにより理解を深めることができました。
引き続き ABC の問題を紹介していきます。
