C++の練習を兼ねて, AtCoder Beginner Contest 021 の 問題C (C – 正直者の高橋くん) を解いてみた.
■感想.
1. 最短距離を計算後(bfs)に, 経路をカウントする部分の方針が見えず, 解説を見て実装した.
2. 幅優先探索の復習が出来たので, 良かった思う.
3. DAG(Directed Acyclic Graph)という新しい知識に触れることが出来たので, 非常に良かったと思う.
4. 訪問済みフラグを, 頂点ベースで実装しても上手く行かなかったので, 辺ベースに変更したところ, AC版となった.
5. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 021解説をご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://www.slideshare.net/chokudai/abc021 #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 pb push_back #define a first #define b second const int MAX = 111; const int MOD = 1e9 + 7; int dist[MAX], dp[MAX]; int memo[MAX][MAX]; // 辺に関する訪問済みフラグ. // グラフを幅優先探索する. // https://ja.wikipedia.org/wiki/幅優先探索 // ※bfsの動作確認用. // @param G: グラフ. // @param s: グラフの探索開始頂点. // @return: 特に無し. void bfs(vvi &G, int s){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // -> スタート地点は, 距離ゼロと見る. dist[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(dist[e] > 0) continue; if(dist[e] == 0 && e != s) dist[e] = dist[u] + 1, q.push(e); } } return; } // DAG上の最短経路数をカウント(bfsっぽい実装). // @param G: グラフ. // @param s: グラフの探索開始頂点. // @return: 特に無し. void countRouteOnDAG(vvi &G, int s){ // 1. 空のキュー. queue<int> q; // 2. スタート地点は, 1通りとする. dp[s] = 1; // 3. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 4. キューから取り出す. int u = q.front(); q.pop(); // 5. 取り出した要素を処理. for(auto &e : G[u]){ // 6. 訪問済であれば, 処理をスキップ. if(memo[u][e] > 0) continue; if(memo[u][e] == 0) dp[e] += dp[u], dp[e] %= MOD, q.push(e), memo[u][e] = 1; } } return; } int main(){ // 1. 入力情報. int N, a, b, M; scanf("%d %d %d %d", &N, &a, &b, &M); a--, b--; vvi G(MAX); vector<P> stock; int x, y; rep(i, M){ scanf("%d %d", &x, &y); x--, y--; G[x].pb(y); G[y].pb(x); stock.pb({x, y}); // DAG構築で使う予定. } // 2. スタート地点 の 頂点 a からの 最短経路 を 探索. bfs(G, a); // rep(i, N) printf("%d ", dist[i]); // puts(""); // 3. DAG作成. // DAG(Directed Acyclic Graph): 閉路がない有効グラフ(解説通り). vvi DAG(MAX); for(auto &p : stock){ int u = p.a, v = p.b; if(dist[p.b] == dist[p.a] + 1) DAG[p.a].pb(p.b); // 頂点 u -> 頂点 v. if(dist[p.a] == dist[p.b] + 1) DAG[p.b].pb(p.a); // 頂点 v -> 頂点 u. } // 4. DAG から 最短経路 の 本数 を カウント(解説通り). countRouteOnDAG(DAG, a); // rep(i, N) printf("%d ", dp[i]); // puts(""); // 5. 出力. printf("%d\n", dp[b]); 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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
[入力例] 7 1 7 8 1 2 1 3 4 2 4 3 4 5 4 6 7 5 7 6 [出力例] 4 ※AtCoderテストケースより [入力例] 7 1 7 9 1 2 1 3 4 2 4 3 4 5 4 6 7 5 7 6 4 7 [出力例] 2 ※AtCoderテストケースより [入力例] 15 3 10 21 3 2 3 1 3 4 3 5 2 6 2 7 1 7 4 8 5 8 5 13 5 9 8 15 13 15 9 15 7 11 7 14 7 12 11 10 14 10 12 10 15 10 [出力例] 10 [入力例] 24 5 11 32 5 2 5 3 5 4 5 1 5 6 6 14 6 15 14 16 16 15 1 12 13 1 10 4 9 3 8 2 7 2 20 19 19 7 7 17 8 17 17 9 10 24 12 24 12 18 13 18 24 17 16 18 22 18 21 17 23 17 11 23 11 21 11 22 [出力例] 8 [入力例] 16 1 16 27 1 2 1 3 1 4 2 3 3 4 2 5 3 5 4 5 4 7 2 6 5 6 5 7 7 8 7 15 6 8 6 14 8 11 8 9 8 10 10 11 10 9 14 9 9 12 15 11 11 13 13 16 12 16 [出力例] 6 [入力例] 18 18 17 30 18 1 18 2 2 3 18 3 1 4 1 5 5 6 1 6 2 7 2 8 2 9 3 10 3 11 4 12 5 12 6 12 7 13 7 8 8 13 9 13 10 14 14 11 10 11 12 15 13 15 13 16 14 16 15 17 15 16 16 17 [出力例] 11 |
■参照サイト
AtCoder Beginner Contest 021