AGC033 C問題：Removing Coins

問題. Removing Coins

頂点の木が与えられる．初めにすべての頂点に1つのコインが置いてある．2人のプレイヤーが交互に次の操作を行う．操作の行えないプレイヤーを負けとする．
コインが置いてある頂点 を1つ選び， にあるコインを取り除く．そして 以外のコインが置いてある任意の頂点 に対して， にあるコインを に近い隣接頂点へ移動する．
2人のプレイヤーが最適な行動を行ったときにどちらが勝つかを判定せよ．

制約：

解法．木の直径

本番で解けなかったので 解説 を参考にした．

コインが置いてある任意の頂点 に対して操作を行ったとき，操作後のコインの配置は を根とした根付き木から葉を取り除いた部分木となる．このとき，葉が取り除かれることから直径は少なくとも 1 小さくなり，直径がちょうど 1 小さくなるための必要十分条件は が直径の端点となることである．また， が直径の端点以外なら直径はちょうど 2 小さくなり，直径が 3 以上小さくなることはない．以上から頂点数が 3 以上のときは直径を 1 または 2 小さくする頂点が存在するので，直径を勝利判定に使えないかを考える．
直径が 0 の木は孤立点のみで先手勝ちとなる．次に，直径が 1 の木は頂点数が 2 の道のみであり，どの頂点を選んでも孤立点となるので後手勝ちとなる．次に直径が 3 のときは，直径を 1 または 2 減らす操作が存在するので先手勝ちとなる．直径が 4 以上の場合も同様に考えると，後手勝ち，先手勝ち，先手勝ち，・・・となり，直径の 3 による剰余が 1 のときのみ後手勝ちとなり，それ以外の場合は先手勝ちとなることが分かる．したがって，直径を線形時間で求めた後に剰余を取って判定することで勝敗が分かる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

template<class W>
struct Tree {
    int n;
    std::vector<std::vector<std::pair<int, W>>> adj;

    explicit Tree(int _n) : n(_n), adj(_n) {}

    void add_edge(const int v1, const int v2, const W w) {
        adj[v1].emplace_back(std::make_pair(v2, w));
        adj[v2].emplace_back(std::make_pair(v1, w));
    }

    std::pair<int, W> Dfs(const int prev, const int cur) {
        std::pair<int, W> res(cur, 0);
        for (const auto &e : adj[cur]) {
            if (prev == e.first) continue;
            auto nxt = Dfs(cur, e.first); nxt.second += e.second;
            if (res.second < nxt.second) res = nxt;
        }
        return res;
    }

    std::pair<int, int> farthest_pair;
    W Diameter() {
        const auto v1 = Dfs(-1, 0), v2 = Dfs(-1, v1.first);
        farthest_pair = std::make_pair(v1.first, v2.first);
        return v2.second;
    }
};

bool Solve() {
    int n;
    cin >> n;

    Tree<int> tree(n);
    for (int i = 0, a, b; i + 1 < n; ++i) {
        cin >> a >> b;
        tree.add_edge(a - 1, b - 1, 1);
    }

    return tree.Diameter() % 3 != 1;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    if (Solve()) cout << "First" << endl;
    else cout << "Second" << endl;

    return 0;
}

道の場合で同様の推論ができたのに木の場合で解くことができずに残念．