ABC 354
Table of Contents
https://atcoder.jp/contests/abc354
A. Exponential Plant
https://atcoder.jp/contests/abc354/tasks/abc354_a
B. AtCoder Janken 2
https://atcoder.jp/contests/abc354/tasks/abc354_b
C. AtCoder Magics
https://atcoder.jp/contests/abc354/tasks/abc354_c
D. AtCoder Wallpaper
https://atcoder.jp/contests/abc354/tasks/abc354_d
E. Remove Pairs
https://atcoder.jp/contests/abc354/tasks/abc354_e
自力 AC.
残りのカードの状態を $S_i$ とし、$S_i$ の状態からペアとなるカードの取り除き方が $m$ 通りあるとき、 $S_i$ からカードを除いた遷移先の状態を $S_{j_1}, \cdots, S_{j_m}$ とする。
$f(S_i)$ をカードの状態が $S_i$ で手番が来たときに勝てるか否かを表すとき
\begin{align*} f(S_i) = \begin{cases} \text{true if } f(S_{j_k}) \text{のうち } f(S_{j_k}) = \text{false} \text{ がある} \\ \text{false otherwise} \end{cases} \end{align*}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N), B(N);
rep(i, N) cin >> A[i] >> B[i];
vector<bool> fixed(1 << N), win(1 << N);
// 使われたカードの状態が state のときに手番が来たときに勝てるか
auto dfs = [&](auto dfs, int state = 0) -> bool {
if (fixed[state]) return win[state];
vector<bool> ret;
// 表
rep(i, N) rep2(j, i + 1, N) {
if (!(state >> i & 1) && !(state >> j & 1) && A[i] == A[j]) {
bool x = dfs(dfs, state | (1 << i) | (1 << j));
ret.push_back(x);
}
}
// 裏
rep(i, N) rep2(j, i + 1, N) {
if (!(state >> i & 1) && !(state >> j & 1) && B[i] == B[j]) {
bool x = dfs(dfs, state | (1 << i) | (1 << j));
ret.push_back(x);
}
}
fixed[state] = true;
for (bool x : ret) {
if (!x) return win[state] = true;
}
return win[state] = false;
};
string ans = "Aoki";
if (dfs(dfs)) ans = "Takahashi";
cout << ans << endl;
}
F. Useless for LIS
https://atcoder.jp/contests/abc354/tasks/abc354_f