C++の練習を兼ねて, AtCoder Beginner Contest 148 の 問題F (F – Playing Tag on Tree) を解いてみた.
■感想.
1. 解答の糸口(※中間地点を考慮する必要があること)に気付くまでに時間かかったものの, 何とかAC版となった.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイトABC 148解説をご覧下さい.
■C++版プログラム(問題F／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
// コメント修正して, 再提出. #include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define pb push_back int du[101010], dv[101010], duv[101010]; // 距離を保存 // グラフを幅優先探索する. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @param d: 探索開始地点からの距離. // @return: 特に無し. void bfs(vvi &G, int s, int* d){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. d[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(d[e] > 0) continue; if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e); } } return; } int main(){ // 1. 入力情報. int N, u, v; scanf("%d %d %d", &N, &u, &v); u--, v--; vvi G(N); rep(i, N - 1){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } // 2. 頂点 u, v から 各頂点までの距離を計算. bfs(G, u, du); bfs(G, v, dv); // 3. 頂点 u, v の 中間地点 m を 取得. // -> 但し, 中間地点については, 頂点 u, v の 間の距離 du[v] が, // 偶数 か 奇数 で 変わってくる点を考慮する必要があるっぽい. // [偶数の場合(du[v] = 8)] // ex. // 24 17 6 // 1 2 // 2 3 // 11 2 // 12 11 // 4 3 // 4 5 // 4 6 // 7 6 // 8 7 // 9 3 // 13 12 // 9 10 // 14 12 // 14 16 // 14 15 // 16 17 // 17 18 // 15 19 // 19 24 // 20 19 // 20 21 // 21 22 // 23 22 // -> 11 が 正解のはず. // // [奇数の場合(du[v] = 3)] // ex. // 9 5 2 // 1 2 // 7 9 // 7 4 // 6 5 // 5 4 // 8 3 // 4 3 // 3 2 // -> 3 が 正解のはず. int m = -1, dm = du[v] / 2; rep(i, N){ if(du[v] % 2 == 0){ if(du[i] == dm && dv[i] == dm){ m = i; break; } }else{ if(du[i] == dm && dv[i] == dm + 1){ m = i; break; } } } // 4. 頂点 m から 各頂点までの距離を計算. bfs(G, m, duv); // 5. 頂点 m から 最も遠い頂点 f を 取得. // ※ 但し, 頂点 v よりも 頂点 u に近いものに限定. int f = -1, df = 0; rep(i, N){ if(df < duv[i] && du[i] < dv[i]) f = i, df = max(df, duv[i]); } // 6. 出力. printf("%d\n", duv[v] + duv[f] - 1); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
[入力例] 5 4 1 1 2 2 3 3 4 3 5 [出力例] 2 ※AtCoderテストケースより [入力例] 5 4 5 1 2 1 3 1 4 1 5 [出力例] 1 ※AtCoderテストケースより [入力例] 2 1 2 1 2 [出力例] 0 ※AtCoderテストケースより [入力例] 9 6 1 1 2 2 3 3 4 4 5 5 6 4 7 7 8 8 9 [出力例] 5 ※AtCoderテストケースより [入力例] 24 17 6 1 2 2 3 11 2 12 11 4 3 4 5 4 6 7 6 8 7 9 3 13 12 9 10 14 12 14 16 14 15 16 17 17 18 15 19 19 24 20 19 20 21 21 22 23 22 [出力例] 11 [入力例] 33 21 3 32 33 30 31 28 29 31 32 30 28 24 28 1 2 2 3 3 4 4 5 4 7 7 6 9 8 9 7 10 9 12 10 10 11 14 11 14 13 15 14 16 15 17 18 15 17 19 18 20 17 21 20 21 22 22 23 24 20 25 24 26 25 27 26 [出力例] 14 [入力例] 9 5 2 1 2 7 9 7 4 6 5 5 4 8 3 4 3 3 2 [出力例] 3 |
■参照サイト
AtCoder Beginner Contest 148