けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題

問題へのリンク

問題概要

頂点数  N のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。

この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂点について、その隣接頂点をすべて黒く塗る。

このとき白い頂点が残っていたら高橋君の勝ち、すべて黒くなったら青木君の勝ちである。双方最善を尽くしたときにどちらが勝つでしょうか?

制約

  •  2 \le N \le 10^{5}

後手の戦略:対称戦略

こういうのはまずはパスで実験すると良さそう。そうすると

  • 長さ偶数では後手必勝
  • 長さ奇数では先手必勝

だとわかる。もう少し考えてみると、後手が勝てるときに後手がやっていることは「対称戦略」だと気づく。すなわち、ツリー全体を完全マッチングで分けられたときに、「高橋君が打った手のマッチングペアに打つ」という真似っこ戦略を行うことで勝てるというわけだ。

一方、頂点数が偶数だからといって常に後手が勝てるとは限らない。具体的には

4
1 2
1 3
1 4

のようなケースがある。このときは先手が「1」に打つとそれだけで勝利が確定する。

先手の戦略:相手に葉しか打てない状態を続ける

さて、先手側にとって一つ有力と思える戦略は

  • 葉を 1 つ選び、そこと繋がっている頂点を塗る。このとき後手は葉しか選べない状態に追い込まれる。

というもの。でもこれをよく考えてみると、この手続きは「ツリー上の最大マッチングを葉から Greedy に求める」という方法そのもの。これで後手の戦略と先手の戦略とが繋がった。すなわち

  • ツリーが完全マッチングをもつなら後手勝ち
  • ツリーが完全マッチングをもたないなら、完全マッチングを作ろうとする過程 (マッチングは切り落とす想定) で「孤立葉が登場」するか「根が最後に孤立」するかのどちらかになり、いずれも先手勝ち

ということになる。葉からマッチングさせていくのは後退解析の要領で queue を使うことで実装できた。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int> >;

Graph G;
vector<int> deg;
vector<bool> seen;

int main() {
    int N; cin >> N;
    G.assign(N, vector<int>());
    deg.assign(N, 0);
    seen.assign(N, 0);
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
        deg[a]++, deg[b]++;
    }
    bool res = true;
    queue<int> que;
    for (int i = 0; i < N; ++i) if (deg[i] == 1) que.push(i);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        if (seen[v]) continue;
        seen[v] = true;

        //COUT(v);
        
        int nv = -1;
        for (auto e : G[v]) if (!seen[e]) nv = e;
        if (nv == -1) {
            res = false;
            break;
        }
        seen[nv] = true;
        for (auto nv2 : G[nv]) {
            if (seen[nv2]) continue;
            deg[nv2]--;
            if (deg[nv2] == 1) que.push(nv2);
        }

        //COUT(nv);
    }
    if (res) cout << "Second" << endl;
    else cout << "First" << endl;
}