C++で対戦相手を捕まえるために必要な最小ラウンド数を求めるプログラム

問題の概要

木構造の辺のリストが [u, v] の形式で与えられるとします。これは頂点 u と頂点 v の間に無向辺が存在することを表しています。さらに、2つの整数 x と y も与えられます。自分は頂点 x におり、対戦相手は頂点 y に位置しています。ゲームは第1ラウンドに自分が移動し、次のラウンドで対戦相手が移動するという形で交互に進行します。対戦相手は、自分の番に移動せずその場にとどまることも選択できます。このとき、対戦相手を捕まえるために必要な最小ラウンド数を求めるのが課題です。

たとえば、入力が edges = [[0, 1], [0, 2], [1, 3], [1, 4]]、x = 0、y = 3 の場合を考えてみましょう。このときの出力は 3 になります。まず自分が頂点 0 から頂点 1 へ移動し、続いて対戦相手は現在いる頂点 3 に留まり、最後に自分が頂点 3 へ移動することで対戦相手を捕まえられるからです。

解決のためのアプローチ

この問題は、幅優先探索（BFS）を2回用いることで効率的に解けます。1回目のBFSで自分の初期位置から各頂点への距離を求め、2回目のBFSで対戦相手が安全に到達できる範囲をシミュレーションします。具体的には、以下の手順に従います。

1. N := 10^5 + 5 とします。

2. サイズ N の配列 visited と visited2 を定義し、両方とも -1 で初期化します。

3. N 個の頂点に対する隣接リスト graph を作成します。

4. 辺リスト edges の各辺 it について、次の操作を行います。

   • graph[it[u]] の末尾に it[v] を追加します。

   • graph[it[v]] の末尾に it[u] を追加します。

5. キュー q を定義し、u を挿入します。visited[u] := 0 とします。

6. q が空でない間、次の処理を繰り返します。

   • node := q の先頭要素を取り出します。

   • graph[node] の各ノード it について、visited[it] が -1 である場合、visited[it] := visited[node] + 1 として it を q に挿入します。

7. q に v を挿入し、visited2[v] := 0、ret := 0 とします。

8. q が空でない間、次の処理を繰り返します。

   • node := q の先頭要素を取り出します。

   • ret := max(ret, 2 * visited[node] - 1) として更新します。

   • graph[node] の各ノード it について、visited2[it] が -1 かつ visited2[node] + 2 < visited[it] を満たす場合、visited2[it] := visited2[node] + 1 として it を q に挿入します。

9. ret を返します。

ポイントは、2回目のBFSにおける条件「visited2[node] + 2 < visited[it]」です。この条件により、対戦相手がその頂点へ移動しても、自分に先を越されて捕まることがない（安全である）ことが保証されます。最終的な答えは、対戦相手が安全に到達できる頂点の中で、自分から最も遠い頂点までの距離をもとに算出されます。

実装例

理解を深めるために、以下のC++による実装をご覧ください。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int visited[N];
int visited2[N];
vector<int> graph[N];
class Solution {
public:
   int solve(vector<vector<int>>& edges, int u, int v) {
      memset(visited, -1, sizeof visited);
      memset(visited2, -1, sizeof visited2);
      for (int i = 0; i < N; i++)
         graph[i].clear();
      for (auto& it : edges) {
         graph[it[0]].push_back(it[1]);
         graph[it[1]].push_back(it[0]);
      }
      queue<int> q;
      q.push(u);
      visited[u] = 0;
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         for (auto& it : graph[node]) {
            if (visited[it] == -1) {
               visited[it] = visited[node] + 1;
               q.push(it);
            }
         }
      }
      q.push(v);
      int ret = 0;
      visited2[v] = 0;
      while (!q.empty()) {
         int node = q.front();
         q.pop();
         ret = max(ret, 2 * (visited[node]) - 1);
         for (auto& it : graph[node]) {
            if (visited2[it] == -1 && visited2[node] + 2 < visited[it]) {
               visited2[it] = visited2[node] + 1;
               q.push(it);
            }
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& edges, int u, int v) {
   return (new Solution())->solve(edges, u, v);
}
int main() {
   vector<vector<int>> edge = {{0, 1}, {0, 2}, {1, 3}, {1, 4}};
   int x = 0, y = 3;
   cout << solve(edge, x, y);
}

入力

[
   [0, 1],
   [0, 2],
   [1, 3],
   [1, 4]
], 0, 3

出力

3