2019-05-07

AtCoder AGC 033 C - Removing Coins (青色, 800 点)

これ大好き！！！

問題へのリンク

問題概要

$N$ 頂点のツリーが与えられる。

初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に

コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き
その頂点以外の全頂点について、そこに乗っているコインすべてを、そこから選んだ頂点へと近づく方向に隣接する頂点へと移動させる

という操作を繰り返す。ここで、操作を行えなくなった方が負け (コインがない状態で盤面を渡された方が負け) である。双方最善を尽くしたとき、先手後手のどちらが勝つか？

制約

$1 \le N \le 2 × 10^{5}$

考えたこと

この手の問題では、

パスグラフ (分岐のないツリー)
スターグラフ (1 つのノードから他の全ノードに辺が伸びたツリー)

といった特殊なツリーに対してどうなるかをまずは考えてみることが大事だと思う。そうしているうちに、自然に解法にたどり着けることも多い。

長さ 1 のパスグラフは、1 枚のコインをとって終わりなので勝ち盤面
長さ 2 のパスグラフは、どちらのコインをとっても、コインのある頂点が 1 個だけ残ってしまうので負け盤面
長さ 3 のパスグラフは、両端いずれかの頂点を選ぶことで、で負け盤面である「長さ 2」を相手に渡せるので、勝ち盤面
長さ 4 のパスグラフは、両端以外の頂点を選ぶことで、負け盤面である「長さ 2」を相手に渡せるので、勝ち盤面
長さ 5 のパスグラフは、両端のいずれかを選ぶと「長さ 4」、それ以外を選ぶと「長さ 3」という、いずれも勝ち盤面しか相手に渡せないので、負け盤面
...

という具合になっていて、

N % 3 == 2 のとき、負け盤面
それ以外のとき、勝ち盤面

ということがわかる。そして後述するように、このパスグラフについての考察は、そのまんま正解解法に直結する。

さらにいろんなグラフ

さらにいろんなグラフで実験してみると、

途中盤面において、各頂点にコインが乗っているか乗っていないかだけが重要で、乗っている場合に何枚乗っているかはどうでもよい
途中盤面において、コインが乗っている頂点は常に連結である
よって、ある頂点についてコインを 0 枚にする操作は、ツリーからその頂点を切り落とす操作であるとみなすことができる

ということが見て取れる。さらにさらに、毎回のターンについて「残っている頂点のなすツリー」において

残っているツリーの葉に相当する頂点を選ぶときは、その頂点以外の葉をすべて切り落とす
それ以外の頂点を選ぶときは、すべての葉を切り落とす

という操作を行うものとみなすことができる

直径に着目

ここまで来ると問題の構造がだいぶわかりやすく特徴づけできた気持ちになって来る。それを踏まえてさらに詰める。

僕は最初はツリーDPになるのかなと思って、どれか 1 つの頂点を根としたツリーを考えてみた。そうすると毎回の操作は「根から伸びた各部分木の深さを 1 ずつ減らすようなイメージ」になっていると思った。つまりツリーは概ね、毎回深さ 1 ずつ小さくなって行く。そうすると最初の根の選び方が重要で、もし根から出ている各部分木の深さが偏っていると、根は一早く切り落とされることになりかねない。

ということは根は木の中心 (直径の中点) であって欲しい気持ちになる。。。というところから木の直径を考えようというところに行き着いた。さらに、ツリーはどんどん小さくなっていくわけだが、ゲーム終了までもつれこむようなボトルネックになっているのは、結局、ツリーの直径ではないかというイメージが錬成された。

結局、さらに考えると

ゲーム中の操作はツリーの直径を必ず 1 か 2 減らす
ツリーの直径の両端点のいずれかを選べば直径は 1 減る
それ以外の頂点を選ぶと、直径は 2 減る

ということがわかった。これで「直径だけ考えれば良い」ということが明快になった。したがって、直径をなす頂点数を $V$ として $V$ を 3 で割ったあまりで判定できる。

#include <iostream>
#include <vector>
using namespace std;


using Graph = vector<vector<int> >;
struct Diameter {
    vector<int> prev;
    pair<int,int> DiameterDFS(const Graph &G, int v, int p) {
        pair<int,int> res(v, 0);
        for (int i = 0; i < (int)G[v].size(); ++i) {
            if (G[v][i] == p) continue;
            pair<int,int> tmp = DiameterDFS(G, G[v][i], v);
            tmp.second++;
            if (tmp.second > res.second) res = tmp, prev[G[v][i]] = v;
        }
        return res;
    }

    vector<int> solve(const vector<vector<int> > &G) {
        prev.assign((int)G.size(), -1);
        pair<int,int> leaf = DiameterDFS(G, 0, -1);
        prev.assign((int)G.size(), -1);
        pair<int,int> t = DiameterDFS(G, leaf.first, -1);
        vector<int> res;
        int cur = t.first;
        while (cur != -1) res.push_back(cur), cur = prev[cur];
        return res;
    }
};


using Graph = vector<vector<int> >;
int N;
Graph G;

int main() {
    cin >> N;
    G.assign(N, vector<int>());
    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);
    }
    Diameter di;
    auto res = di.solve(G);    
    int V = res.size();
    if (V % 3 == 2) cout << "Second" << endl;
    else cout << "First" << endl;
}