ABC067D

D - Fennec VS. Snuke

N個のノードからなる木において、ノード1とノードNのそれぞれから、自分のノードと隣接している、他人のノードでないノードを取ることができるというルールで陣取りを行った場合、取るノードが先に無くならないのはどちらかという問題です。

木の問題は、何問か解いたことがあったため、解説を見ずに解くことができました。

木は個人的に思い入れのあるデータ構造なので、そういった理由もあるのかもしれません。

まず、隣接リストに木を読み込みます。

/* typedef vector<vector<int>> Tree; */

  int n; cin >> n;
  Tree t(n);
  for (int i = 0; i < n-1; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    t[a].push_back(b);
    t[b].push_back(a);
  }

次に、幅優先探索を、ノード1とノードNの双方から行います。

（コード上では0-indexedなので、とから）

  auto bfs = [&](int u, int d[]) {
    queue<int> que;
    que.push(u);
    d[u] = 1;
    while (!que.empty()) {
      int u = que.front(); que.pop();
      for (int v : t[u]) {
        if (d[v] == 0) {
          que.push(v);
          d[v] = d[u] + 1;
        }
      }
    }
  };

  int fd[n] = {}, sd[n] = {};
  bfs(0, fd);
  bfs(n-1, sd);

最後に、ノード1からの距離がノードNからの距離以下であればノード1の陣地数を増やし、そうでなければノードNの陣地数を増やします。

これは、ルールと木構造の性質上、あるノードに早く辿り着いた方が、そのノードから伸びる、相手陣地に繋がるノード以外のノードを確実に取ることができるからです。

陣地数がノード1の方が多ければノード1の勝利、そうでなければノードNの勝利となります。

（同じ場合は、最終的にノード1が取る陣地が無くなるので、ノードNの勝利です）

  int fd[n] = {}, sd[n] = {};
  bfs(0, fd);
  bfs(n-1, sd);

  int fc = 0, sc = 0;
  for (int i = 0; i < n; i++) {
    if (fd[i] <= sd[i]) fc++;
    else sc++;
  }

  cout << (fc > sc ? "Fennec" : "Snuke") << endl;

今回の問題は気持ちよく解くことができました。

では。