Atcoder Regular Contest 079 F. Namori Grundy

Atcoder Regular Contest 079 F. Namori Grundy

F: Namori Grundy - AtCoder Regular Contest 079 | AtCoder

感想

こういうグラフをNamoriグラフというらしい。

解法

まずグラフの形状が常に閉路を一つ含み、そこから木が外側に向かって生えたようなグラフになることに気づかねばならない。証明は絵を描いてごにょればわかる。

こうすると閉路に含まれない頂点のgrundy数$\ g\ $は葉から決めていくことで確定する。あとは閉路の部分の$\ g\ $が矛盾なく決定できるかどうかを見る。

さて、閉路中のある頂点$\ v\ $に注目し、$\ g\ $がすでに確定している遷移先の$\ g\ $の$\ mex\ $を$\ m\ $とすると、まだ確定していない遷移先$\ u\ $について、$\ g_u = m\ $となるならば、この数を加えた$\ mex\ $が$\ g_v\ $になり、$\ g_u \neq m\ $ならば$\ g_v = m\ $とすれはよいので、結局この2つを$\ g_v\ $として試して整合性をチェックすれば良い。

実装は汚くなってしまった。

実装

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

static const int INF = 0x3f3f3f3f;

vector<int> g[202020];
int grundy[202020];
bool used[202020];

int dfs(int v, int prev) {
        used[v] = true;
        set<int> s;
        for (auto u : g[v]) if (u != prev) {
                if (used[u]) s.insert(grundy[u]);
                else s.insert(dfs(u, v));
        }
        if (s.count(-1)) return grundy[v] = -1;
        int g = 0;
        while (s.count(g)) g ++;
        return grundy[v] = g;
}

int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++) {
                int p;
                cin >> p;
                p --;
                g[p].push_back(i);
        }
        memset(grundy, -1, sizeof(grundy));
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        int start;
        for (int i = 0; i < n; i ++) {
                if (grundy[i] == -1) {
                        start = i;
                        break;
                }
        }
        set<int> s;
        for (auto t : g[start]) {
                if (grundy[t] == -1) continue;
                s.insert(grundy[t]);
        }
        int mi1 = 0, mi2 = 0;
        while (s.count(mi1)) mi1 ++;
        s.insert(mi1);
        while (s.count(mi2)) mi2 ++;
        grundy[start] = mi1;
        int check[202020] = { 0 };
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) check[i] = -1;
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) used[i] = false;
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        set<int> s1;
        for (auto t : g[start])  s1.insert(grundy[t]);
        int gr = 0;
        while (s1.count(gr)) gr ++;
        if (gr == grundy[start]) {
                cout << "POSSIBLE" << endl;
                return 0;
        }
        for (int i = 0; i < n; i ++) if (check[i] == -1) grundy[i] = -1;
        grundy[start] = mi2;
        for (int i = 0; i < n; i ++) if (grundy[i] == -1) used[i] = false;
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i, -1);
        set<int> s2;
        for (auto t : g[start]) s2.insert(grundy[t]);
        gr = 0;
        while (s2.count(gr)) gr ++;
        if (gr == grundy[start]) {
                cout << "POSSIBLE" << endl;
                return 0;
        }
        cout << "IMPOSSIBLE" << endl;
        return 0;
}