AOJ2376 DisconnectedGame

問題ページ

連結成分が2個のグラフが与えられたときを考える．各連結成分の大きさを ，辺の数を とすると，操作できる回数は 回である．よって，この回数の偶奇でどちらが勝つか判定することができる． の偶奇は で判定でき，0もしくは1のときは偶数で，2もしくは3のときは奇数である．したがって 連結成分の頂点数 mod 4 をkeyに のDPをすることで答えが求まるが，これではTLEになってしまう．

2つの連結成分をつなげるような辺を追加したときに，連結成分内同士の頂点を結ぶ辺を追加できる回数がどのように変化するか考える． より の少なくとも一方が偶数であれば追加できる回数の偶奇が反転し，そうでなければ偶奇は変化しない．よって dp[頂点数が偶数の連結成分の数][頂点数が奇数の連結成分の数][同じ連結成分の頂点を結ぶ辺を追加できる回数 mod 2] = 勝敗 とすることでDPの状態数を に抑えられる．

dp[i][j][k] の遷移先は以下の4つで Lose の状態が一つでもあれば dp[i][j][k] = Win

• 頂点数が偶数同士をつなげる
  偶数の連結成分が1減少し，辺を追加できる回数の偶奇も変化 dp[i-1][j][!k]
• 頂点数が偶数と奇数をつなげる (偶数同士と同じ遷移をするので実質無視)
  偶数の連結成分が1減少し，辺を追加できる回数の偶奇も変化 dp[i-1][j][!k]
• 頂点数が奇数同士をつなげる
  奇数の連結成分が2減少，偶数が1増加 dp[i+1][j-2][k]
• 同じ連結成分の頂点をつなぐ
  kが偶数のときに行っても相手に同じ操作をされて戻されるだけ，kが奇数のときのみ行える dp[i][j][!k]

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
struct UnionFind {  
    vector<int> par, s;  
    UnionFind(int n=2e5) { init(n); }  
    void init(int n) {   
        s.assign(n, 1); par.resize(n);   
        iota(par.begin(), par.end(), 0);  
    }  
    int find(int x) {  
        if(par[x] == x) return x;  
        return par[x] = find(par[x]);  
    }  
    void unite(int x, int y) {  
        x = find(x);  
        y = find(y);  
        if(x == y) return;  
        if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];  
        else par[y] = x, s[x] = s[x] + s[y];  
    }  
    bool same(int x, int y) { return find(x) == find(y); }  
    int size(int x) { return s[find(x)]; }  
};  
  
bool memo[1005][1005][2], dp[1005][1005][2];  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<string> s(n);  
    REP(i, n) cin >> s[i];  
  
    ll m = 0;  
    UnionFind uf(n);  
    REP(i, n) FOR(j, i+1, n) if(s[i][j] == 'Y') uf.unite(i, j), m++;  
    ll odd = 0, even = 0, rest = 0;  
    REP(i, n) if(uf.find(i) == i) {  
        ll sz = uf.size(i);  
        if(sz%2) odd++;  
        else even++;  
        rest ^= sz*(sz-1)/2%2;  
    }  
    rest ^= m%2;  
  
    function<bool(ll,ll,ll)> dfs = [&](ll x, ll y, ll z) {  
        if(memo[x][y][z]) return dp[x][y][z];  
        if(x+y==2) return z==1;  
  
        bool ret = false;
        if(x+y>2 && x>=1) ret |= !dfs(x-1, y, !z);    // 偶数同士
        // if(x+y>2 && x>=1) ret |= !dfs(x-1, y, !z); // 偶数と奇数
        if(x+y>2 && y>=2) ret |= !dfs(x+1, y-2, z);   // 奇数同士
        if(z==1) ret |= !dfs(x, y, !z);               // 同じ連結成分内の辺
  
        memo[x][y][z] = true;  
        return dp[x][y][z] = ret;  
    };  
    bool ret = dfs(even, odd, rest);  
  
    if(ret) cout << "Taro" << endl;  
    else cout << "Hanako" << endl;  
  
    return 0;  
}