C++の練習を兼ねて, AtCoder Grand Contest 004 の 問題D (Teleporter) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 004 解説をご覧下さい.
■C++版プログラム(問題D／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 |
// 解き直し. // https://img.atcoder.jp/data/agc/004/editorial.pdf #include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; using P = pair<int, 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 repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second #define pb push_back int bef[101010]; // テレポーターの情報. int cur[101010]; // テレポーターの情報(コピー). int d[101010]; // 首都 からの 距離 を 保存. int memo[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, K, ans = 0; scanf("%d %d", &N, &K); vvi G(N); rep(i, N){ scanf("%d", &bef[i]); bef[i]--; cur[i] = bef[i]; if(i == 0){ if(bef[i]) cur[i] = 100000; // 首都から出る辺は首都へ戻る自己ループ. continue; } G[i].pb(bef[i]); G[bef[i]].pb(i); } // 2. 首都 から 各頂点までの距離を計算. bfs(G, 0, d); // 3. 首都 から 遠い順に並び替え. priority_queue<P> pq; repx(i, 1, N) pq.push({d[i], i}); // while(!pq.empty()){ // P p = pq.top(); // pq.pop(); // printf("dist=%d v=%d\n", p.a, p.b); // } // 4. テレポーターの転送先変更. // -> 首都から遠い町から, 首都に向かって, 進み, // (K - 1)進んだら, 終了 を 繰り返す. while(!pq.empty()){ // 頂点を一つ取得. P v = pq.top(); pq.pop(); // 訪問済みか確認, 未訪問なら訪問済みへ. if(memo[v.b]) continue; memo[v.b] = 1; // 親頂点へ繰り返し移動. int move = 0; int c = v.b; // 子頂点. int p = bef[c]; // 親頂点. while(p > 0 && !memo[p]){ if(move == K - 1) break; move++; // 移動距離. memo[p] = 1; // 訪問済みに設定. c = p; // 子頂点. p = bef[c]; // 親頂点. } // テレポーターの転送先が, 首都でない場合は, 首都に変更. if(p && move == K - 1) cur[c] = 100000; } // rep(i, N) printf("%d ", bef[i]); // puts(""); // rep(i, N) printf("%d ", cur[i]); // puts(""); // 5. テレポーターの転送先変更回数を確認. rep(i, N) if(bef[i] != cur[i]) ans++; printf("%d\n", ans); 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 |
[入力例] 3 1 2 3 1 [出力例] 2 ※AtCoderテストケースより [入力例] 4 2 1 1 2 2 [出力例] 0 ※AtCoderテストケースより [入力例] 8 2 4 1 2 3 1 2 3 4 [出力例] 3 ※AtCoderテストケースより [入力例] 13 2 5 1 1 2 9 3 3 6 4 4 3 11 11 [出力例] 5 [入力例] 20 3 11 1 2 3 4 4 2 7 8 8 12 13 15 10 10 15 3 17 17 19 [出力例] 6 |
■参照サイト
AtCoder Grand Contest 004