最高に好きな問題
問題概要
頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。
この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂点について、その隣接頂点をすべて黒く塗る。
このとき白い頂点が残っていたら高橋君の勝ち、すべて黒くなったら青木君の勝ちである。双方最善を尽くしたときにどちらが勝つでしょうか？
制約
後手の戦略：対称戦略
こういうのはまずはパスで実験すると良さそう。そうすると
- 長さ偶数では後手必勝
- 長さ奇数では先手必勝
だとわかる。もう少し考えてみると、後手が勝てるときに後手がやっていることは「対称戦略」だと気づく。すなわち、ツリー全体を完全マッチングで分けられたときに、「高橋君が打った手のマッチングペアに打つ」という真似っこ戦略を行うことで勝てるというわけだ。
一方、頂点数が偶数だからといって常に後手が勝てるとは限らない。具体的には
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; }
