Fennec VS. Snuke [AtCoder Regular Contest 078 D]

http://arc078.contest.atcoder.jp/tasks/arc078_b

解法

http://arc078.contest.atcoder.jp/submissions/1424748

プレイヤーには貪欲法が存在する。
頂点1と頂点Nの間の木のパスがなるべく取れるほど、塗れる頂点が多くなる。
その為、まずは、頂点1と頂点Nの間を順番に貪欲に埋めていく。
あとは、その後に塗れる所を塗れるまで塗ったときに、どちらが先に塗れなくなるかという問題となる。
貪欲に塗ったときに塗れてる数を見ると答えが分かる。

以下のコードでは(過実装であるが)HL分解を(LCA部分で)使いつつ頂点間の距離を高速にもとめている。
頂点1と頂点Nの間にある頂点は、dist(1,i) + dist(i,N) = dist(1,N)を満たしている。
この頂点を頂点1, 頂点Nから近い順に順番に塗っていく。
そこから深さ優先で塗れるだけ塗る。あとは、塗った数をカウントする。
「フェネックの数 <= すぬけくん」なら「すぬけくん」の勝ち
さもなければ「フェネック」の勝ち

他の人の解答
面倒な塗り方をしてしまったが、ある頂点iについて、

• dist(1,i) <= dist(N,i)ならばフェネックで塗る
• さもなければすぬけくんで塗る

のが簡単なやり方である。
kawateaさんのFA解答

int N;
vector<int> E[101010];
int col[101010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu) {
    fore(to, E[cu]) if (!col[to]) {
        col[to] = col[cu];
        dfs(to);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    HLDecomposition hld;
    hld.init(N);
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        hld.add(a, b);
        E[a].push_back(b);
        E[b].push_back(a);
    }
    hld.build();
 
    vector<pair<int, int>> v;
    rep(i, 0, N) if(hld.distance(0, N - 1) == hld.distance(0, i) + hld.distance(i, N - 1)){
        v.push_back({ hld.distance(0, i), i });
    }
    sort(v.begin(), v.end());
 
    int i = 0;
    int j = v.size() - 1;
    while (i < j) {
        col[v[i].second] = 1;
        col[v[j].second] = 2;
        i++; j--;
    }
    if (i == j) col[v[i].second] = 1;
    dfs(0);
    dfs(N - 1);
    fore(p, v) dfs(p.second);
 
    int a = 0, b = 0;
    rep(i, 0, N) {
        if (col[i] == 1) a++;
        else if (col[i] == 2) b++;
    }
 
    if (a <= b) printf("Snuke\n");
    else printf("Fennec\n");
}