東京工業大学プログラミングコンテスト2015 M - コインと無向グラフ

本当に Nim だった(grundy 数かもとも思っていたのだけれど)

問題

ttpc2015.contest.atcoder.jp

解法

実は, 「距離が奇数のものからの Nim」ということで解くことが出来ます。

距離が奇数のもの全体の状態が (n1, n2, ..., nk) で表されるとしましょう。
まず n1 = n2 = ... = nk = 0 の場合は動かせるコインが無いので負け確ですね。
また, それ以外の場合で n1^n2^...^nk = 0 の時は, 距離が奇数のものを動かせばどうしても n1^n2^...nk != 0 の状態になってしまいますし, 距離が偶数のものを動かすと xor の和が 0 になるかもしれませんがその動かしたコインを後手の人がそのまま動かせばまた同じ(n1, n2, ..., nk) の状態に戻ってしまいます(距離が偶数の位置にコインが移動するので距離が奇数の場所に関しては何も影響が無いようになってしまう)。

また, xor の和が 0 で無い時は Nim と同じようにして xor の和を 0 にすることが出来ます。
よって, 上で示した Nim で解けることがわかりました。

最初 ARC 38 の C 問題と同じように grundy 数でできるんじゃないかと思ったんですがこれは豆を動かす数が毎回 1 つずつだから出来た所業ですね。

const int MAXN = 100010;
const int INF = 1e9;
vector<int> G[MAXN];
int C[MAXN], d[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> C[i];
    while (M--) {
        int v, w;
        cin >> v >> w;
        G[v].push_back(w);
        G[w].push_back(v);
    }
    queue<int> que;
    que.push(0);
    for (int i = 1; i < N; i++) d[i] = INF;
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int ch : G[v]) {
            if (d[ch] == INF) {
                d[ch] = d[v]+1;
                que.push(ch);
            }
        }
    }
    int x = 0;
    for (int i = 0; i < N; i++) {
        if (d[i]%2) x ^= C[i];
    }
    if (x==0) cout << "Second" << endl;
    else cout << "First" << endl;
    return 0;
}