AtCoder Regular Contest 078 D Fennec VS Snuke

問題

atcoder.jp

問題概要

$N$ 個のマスと $N - 1$ 本の道を持つグラフがある。
Fennecは $1$ 番目、Snukeは $N$ 番目のマスからそれぞれ別の色を塗る。
先にマスに色を塗れなくなるのはどちらか。

考察 and 解説

基本的に先に塗れるマスが多い方が勝つ。

このグラフを各道のコストが $1$ の無向グラフに見立て $1$ と $N$ から、各マスへの最短コストを求める。

このとき、 $2$ 人の勝利条件は

Fennec
- 先に塗れるマスが Snuke より多い。
Snuke
- 塗れるマスが同じか、先に塗れるマスが Fennec より多い。

注意なのは先に塗れるマスが同じときで、この場合は最初にFennecが塗るマスがなくなり負けてしまう。

各マスへの最短路計算にはダイクストラ法を使うと良い。(プライオリティキューを使った実装で $O(Nlog N)$ )

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
struct edge { long long to, cost;};
typedef pair<long long, long long> P_dij;

/* params
 * @s -> start, n -> 要素数, G -> グラフ, d -> 結果(参照渡し)
*/
void dijkstra(const long long s, const long long n,
  vector< vector<edge> > const &G, vector<long long> & d){
  d.resize(n);
  for(int i=0; i<n; i++) d[i] = INF; 
  priority_queue<P_dij, vector<P_dij>, greater<P_dij>> que;
  d[s] = 0;
  que.push(P_dij(0, s));
  while (!que.empty()) {
    P_dij p = que.top();
    que.pop();
    long long v = p.second;
    if(d[v] < p.first)continue;
    for(int i=0;i<G[v].size(); i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(P_dij(d[e.to], e.to));
      }
    }
  }
}

/* END END END */
int main() {
  int n;
  cin >> n;
  vector<vector<edge>> G(n+1);
  
  int a,b;
  rep(i, n-1) {
    cin >> a >> b;
    --a, --b;
    G[a].push_back({b, 1});
    G[b].push_back({a, 1});
  }

  vector<ll> d1, d2;
  dijkstra(0, n, G, d1);
  dijkstra(n-1, n, G, d2);

  int cntf = 0, cnts = 0;
  for (int i = 0; i < n; ++i) {
    if (d1[i] < d2[i]) cntf += 1;
    else if (d1[i] == d2[i]) cntf += 1;
    else cnts += 1;
  }

  if (cnts > cntf or cnts == cntf) {
    cout << "Snuke" << endl;
  } else {
    cout << "Fennec" << endl;
  }
}