はむへい’s diary

ねむいです。

AtCoder Beginner Contest 067 D - Fennec VS. Snuke

問題URL

D - Fennec VS. Snuke

解法

与えられるグラフは木なので、頂点1から頂点Nまでの経路は一通りです。
お互いにその経路上に自分の陣地を伸ばしていき、その後互いが塗ることのできる頂点に色を塗っていくことが互いにとって最適な戦略です。
まだその経路上の頂点が全て塗られてないうちに経路上の頂点以外を塗ってしまうと、相手が到達できる範囲を広げてしまうことになるからです。
これを幅優先探索を用いてシュミレーションすれば、答えを得ることができます。 計算量はO(N)です。

ACしたコード

atcoder.jp

#include <bits/stdc++.h>

using namespace std;

int main(){
    int N;cin >> N;
    vector<vector<int>> E(N);
    for(int i = 0;i < N - 1;i++){
        int a,b;cin >> a>> b;
        a--,b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    vector<int> flag(N, -1);
    flag.front() = 0;
    flag.back() = 1;
    queue<int> que;
    que.push(0);
    que.push(N-1);
    while(!que.empty()){
        int q = que.front();
        que.pop();
        for(auto a : E[q]){
            if(flag[a] == -1){
                flag[a] = flag[q];
                que.push(a);
            }
        }
    }
    int F = 0,S = 0;
    for(auto a : flag){
        if(a == 0)F++;
        else S++;
        //cout<<a<<endl;
    }

    if(S < F){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
}