impartial gameではあるが結合の操作が和でないのでだめだった。 しかし調べれば方法がでてきそうではある。

ちゃんと見ればDP不要にして常に$O(1)$にできるのではという気もしている。

solution

偶奇でいい感じに。$|V|$が奇数なら辺の数$|E|$を求めるのを除いて$O(1)$。 $|V|$が偶数ならDPで最後に残る連結成分の大きさの偶奇を決めて$O(|V|^2)$。

ゲームを進行させると最終的に連結成分はふたつ残り、それぞれ完全グラフを成す。 その頂点数をそれぞれ$a, b$とする。 このとき最終的に${}_aC_2 + {}_bC_2$本の辺があり、初期状態で存在する辺の数を${}_aC_2 + {}_bC_2 + |E|$の偶奇で答えが定まる。 $a + b = n$なので${}_aC_2 + {}_bC_2 = \frac{(a + b)^2 - 2ab - (a + b)}{2} = {}_nC_2 - ab$。 $n = a + b$が奇数なら$ab$は常に偶数。 $n = a + b$が偶数なら$ab$は偶数にも奇数にもなりうるので、これだけが両者の争点となる。 与えられたグラフの連結成分に大きさが偶数のものが$e$個 奇数のものが$o$個存在するとして、$O((e + o)^2)$のDPでその結果を求めればよい。 base caseとなる$(e, o) = (2, 0), (0, 2)$の場合にどちらが勝つのかには$|V|, \; |E|$だけでなく$e + o$の偶奇も絡むことに注意。

implementation

DPはloopで回すのが面倒だったのでメモ化した。

#include <cstdio>
#include <vector>
#include <map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int main() {
    // input
    int n; scanf("%d", &n);
    auto g = vectors(n, n, false);
    int e = 0;
    repeat (y, n) repeat (x, n) {
        char c; scanf(" %c", &c);
        e += c == 'Y';
        if (c == 'Y') {
            g[y][x] = true;
            g[x][y] = true;
        }
    }
    e /= 2;
    // solve
    bool result;
    if (n % 2 == 1) {
        result = (n*(n-1)/2 - e) % 2;
    } else {
        vector<bool> used(n);
        function<int (int)> go = [&](int i) {
            used[i] = true;
            int size = 1;
            repeat (j, n) if (g[i][j]) {
                if (not used[j]) {
                    size += go(j);
                }
            }
            return size;
        };
        int even = 0;
        int odd = 0;
        repeat (i, n) {
            if (not used[i]) {
                int size = go(i);
                (size % 2 == 0 ? even : odd) += 1;
            }
        }
        map<pair<int, int>, bool> memo;
        function<bool (int, int)> dp = [&](int a, int b) {
            pair<int, int> key = { a, b };
            if (memo.count(key)) return memo[key];
            bool result = false;
            assert (a + b >= 2);
            assert (not (a == 1 and b == 1));
            if (a == 2 and b == 0) {
                if ((n*(n-1)/2 + e + odd + even) % 2 == 1) result = true;
            } else if (a == 0 and b == 2) {
                if ((n*(n-1)/2 + e + odd + even) % 2 == 0) result = true;
            } else {
                if (a >= 2            and not dp(a-1, b  )) result = true;
                if (a >= 1 and b >= 1 and not dp(a-1, b  )) result = true;
                if (           b >= 2 and not dp(a+1, b-2)) result = true;
            }
            return memo[key] = result;
        };
        result = dp(even, odd);
    }
    // output
    printf("%s\n", result ? "Taro" : "Hanako");
    return 0;
}