AtCoder Beginner Contest 067 D - Fennec VS. Snuke
問題URL
解法
与えられるグラフは木なので、頂点から頂点までの経路は一通りです。
お互いにその経路上に自分の陣地を伸ばしていき、その後互いが塗ることのできる頂点に色を塗っていくことが互いにとって最適な戦略です。
まだその経路上の頂点が全て塗られてないうちに経路上の頂点以外を塗ってしまうと、相手が到達できる範囲を広げてしまうことになるからです。
これを幅優先探索を用いてシュミレーションすれば、答えを得ることができます。
計算量はです。
ACしたコード
#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; } }