C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題E (E – Hopscotch Addict) を解いてみた.
■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, グラフを “3倍化” するというのが, 何のことか理解出来なかったが, 多分こうだろうという実装で, AC版まで行ったので, 大きなズレは無かったと思う.
3. TLE版 と AC版 を 掲載した.
※1. TLE版 を AC版 に 修正する訓練を積めたので, 貴重な経験となったと思う.
※2. AC版は, 50 ～ 51ms で通過したので, 十分高速化出来たと思う.
本家のサイトABC 132解説をご覧下さい.
■C++版プログラム(問題E／TLE版).
|
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 |
// 解き直し. // ABC 132解説. // https://img.atcoder.jp/abc132/editorial.pdf #include <bits/stdc++.h> using namespace std; const int MAX_V = 1e5; int memo[321123]; struct Edge{ int f, t, w; }; struct Graph{ int V, E; struct Edge* edge; }; struct Graph* build(int V, int E){ struct Graph* graph = new Graph; graph->V = V; graph->E = E; graph->edge = new Edge[E]; return graph; } // 幅優先探索. // https://ja.wikipedia.org/wiki/幅優先探索 // グラフを幅優先探索する. // ※bfsの動作確認用. // @param graph: グラフ. // @param s: 探索開始の頂点番号. // @param g: 探索終了の頂点番号. // @param M: 辺数. // @return: 特に無し. void bfs(struct Graph* graph, int s, int g, int M){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); // 4. キュー q が 空になるまで, 探索. while(!q.empty()) { // 5. 頂点 u を キュー q から取り出す. int u = q.front(); q.pop(); // 6. 頂点 u が ゴールだったら終了. // -> TLE対策. if(u == g) break; // 7. 取り出した要素を処理. for(int i = 0; i < M; i++){ int a = graph->edge[i].f; int b = graph->edge[i].t; int w = graph->edge[i].w; // 7-1. 頂点u の 隣接する頂点b が, 未訪問だったら, キュー q に追加. if(u == a && memo[b] == 0 && b != s){ q.push(b); // 頂点b を キュー q に追加. // 頂点b に 距離memo[a] プラス 1 を 加算. memo[b] += memo[a]; memo[b]++; } // ※※※ 本問は, 有向グラフを考えているので, コメントアウト ※※※. // 7-2. 頂点u の 隣接する頂点a が, 未訪問だったら, キュー q に追加. // if(u == b && memo[a] == 0 && a != s){ // q.push(a); // 頂点a を キュー q に追加. // // 頂点a に 距離memo[b] プラス 1 を 加算. // memo[a] += memo[b]; // memo[a]++; // } } } } int main() { // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); // 2. グラフ作成. // 解説通り, グラフを3倍化？してみる. // 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を 張る. // 具体的には, // u0 = u + i * 3, u1 = u + 1, u2 = u + MAX_V * 2 // v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2 struct Graph* graph = build(N * 3, M * 3); for(int i = 0; i < M * 3; i += 3){ int u, v; scanf("%d %d", &u, &v); u--, v--; // u0 -> v1 graph->edge[i + 0].f = u; graph->edge[i + 0].t = v + MAX_V * 1; graph->edge[i + 0].w = 1; // u1 -> v2 graph->edge[i + 1].f = u + MAX_V * 1; graph->edge[i + 1].t = v + MAX_V * 2; graph->edge[i + 1].w = 1; // u2 -> v0 graph->edge[i + 2].f = u + MAX_V * 2; graph->edge[i + 2].t = v; graph->edge[i + 2].w = 1; } // for(int i = 0; i < M * 3; i++){ // int f = graph->edge[i].f; // int t = graph->edge[i].t; // int w = graph->edge[i].w; // cout << "i=" << i << " f=" << f << " t=" << t << " w=" << w << endl; // } // 3. スタート地点, ゴール地点. int S, T; scanf("%d %d", &S, &T); S--, T--; // 4. S0 -> T0 の 最短距離 を 計算. bfs(graph, S, T, M * 3); // for(int i = 0; i < N * 3; i++) cout << memo[i] << " "; // cout << endl; // 5. 後処理. int ans = memo[T] / 3; if(ans == 0) printf("%d\n", -1); else 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 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 |
[入力例] 4 4 1 2 2 3 3 4 4 1 1 3 [出力例(debug版)] i=0 f=0 t=100001 w=1 i=1 f=100000 t=200001 w=1 i=2 f=200000 t=1 w=1 i=3 f=1 t=100002 w=1 i=4 f=100001 t=200002 w=1 i=5 f=200001 t=2 w=1 i=6 f=2 t=100003 w=1 i=7 f=100002 t=200003 w=1 i=8 f=200002 t=3 w=1 i=9 f=3 t=100000 w=1 i=10 f=100003 t=200000 w=1 i=11 f=200003 t=0 w=1 0 9 6 3 0 0 0 0 0 0 0 0 2 ※経路確認 始点: 0 終点: 2 けんけんぱの経路: 0 -> 100001 -> 200002 -> 3 -> 100000 -> 200001 -> 2 => OK ※AtCoderテストケースより [入力例] 6 8 1 2 2 3 3 4 4 5 5 1 1 4 1 5 4 6 1 6 [出力例(debug版)] i=0 f=0 t=100001 w=1 i=1 f=100000 t=200001 w=1 i=2 f=200000 t=1 w=1 i=3 f=1 t=100002 w=1 i=4 f=100001 t=200002 w=1 i=5 f=200001 t=2 w=1 i=6 f=2 t=100003 w=1 i=7 f=100002 t=200003 w=1 i=8 f=200002 t=3 w=1 i=9 f=3 t=100004 w=1 i=10 f=100003 t=200004 w=1 i=11 f=200003 t=4 w=1 i=12 f=4 t=100000 w=1 i=13 f=100004 t=200000 w=1 i=14 f=200004 t=0 w=1 i=15 f=0 t=100003 w=1 i=16 f=100000 t=200003 w=1 i=17 f=200000 t=3 w=1 i=18 f=0 t=100004 w=1 i=19 f=100000 t=200004 w=1 i=20 f=200000 t=4 w=1 i=21 f=3 t=100005 w=1 i=22 f=100003 t=200005 w=1 i=23 f=200003 t=5 w=1 0 3 6 3 3 6 0 0 0 0 0 0 0 0 0 0 0 0 2 ※経路確認 始点: 0 終点: 5 けんけんぱの経路: 0 -> 100004 -> 200000 -> 4 -> 100000 -> 200003 -> 5 => OK ※AtCoderテストケースより [入力例] 7 9 1 2 2 3 3 4 4 5 5 1 1 4 5 2 1 5 4 6 2 5 [出力例(debug版)] i=0 f=0 t=100001 w=1 i=1 f=100000 t=200001 w=1 i=2 f=200000 t=1 w=1 i=3 f=1 t=100002 w=1 i=4 f=100001 t=200002 w=1 i=5 f=200001 t=2 w=1 i=6 f=2 t=100003 w=1 i=7 f=100002 t=200003 w=1 i=8 f=200002 t=3 w=1 i=9 f=3 t=100004 w=1 i=10 f=100003 t=200004 w=1 i=11 f=200003 t=4 w=1 i=12 f=4 t=100000 w=1 i=13 f=100004 t=200000 w=1 i=14 f=200004 t=0 w=1 i=15 f=0 t=100003 w=1 i=16 f=100000 t=200003 w=1 i=17 f=200000 t=3 w=1 i=18 f=4 t=100001 w=1 i=19 f=100004 t=200001 w=1 i=20 f=200004 t=1 w=1 i=21 f=0 t=100004 w=1 i=22 f=100000 t=200004 w=1 i=23 f=200000 t=4 w=1 i=24 f=3 t=100005 w=1 i=25 f=100003 t=200005 w=1 i=26 f=200003 t=5 w=1 6 0 6 6 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ※経路確認 始点: 1 終点: 4 けんけんぱの経路: 1 -> 100002 -> 200003 -> 4 => OK [入力例] 7 9 1 2 1 3 4 1 2 3 3 4 6 7 7 5 5 6 4 5 3 5 [出力例(debug版)] i=0 f=0 t=100001 w=1 i=1 f=100000 t=200001 w=1 i=2 f=200000 t=1 w=1 i=3 f=0 t=100002 w=1 i=4 f=100000 t=200002 w=1 i=5 f=200000 t=2 w=1 i=6 f=3 t=100000 w=1 i=7 f=100003 t=200000 w=1 i=8 f=200003 t=0 w=1 i=9 f=1 t=100002 w=1 i=10 f=100001 t=200002 w=1 i=11 f=200001 t=2 w=1 i=12 f=2 t=100003 w=1 i=13 f=100002 t=200003 w=1 i=14 f=200002 t=3 w=1 i=15 f=5 t=100006 w=1 i=16 f=100005 t=200006 w=1 i=17 f=200005 t=6 w=1 i=18 f=6 t=100004 w=1 i=19 f=100006 t=200004 w=1 i=20 f=200006 t=4 w=1 i=21 f=4 t=100005 w=1 i=22 f=100004 t=200005 w=1 i=23 f=200004 t=5 w=1 i=24 f=3 t=100004 w=1 i=25 f=100003 t=200004 w=1 i=26 f=200003 t=4 w=1 6 3 0 9 6 3 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 ※経路確認 始点: 2 終点: 4 けんけんぱの経路: 2 -> 100003 -> 200000 -> 1 -> 100002 -> 200003 -> 4 => OK |
■C++版プログラム(問題E／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 |
// 解き直し. // ABC 132解説. // https://img.atcoder.jp/abc132/editorial.pdf #include <bits/stdc++.h> using namespace std; const int MAX_V = 1e5; int memo[321123]; vector<int> graph[321123]; // 幅優先探索. // https://ja.wikipedia.org/wiki/幅優先探索 // グラフを幅優先探索する. // ※bfsの動作確認用. // @param s: 探索開始の頂点番号. // @param g: 探索終了の頂点番号. // @return: 特に無し. void bfs(int s, int g){ // 1. 空のキュー. queue<int> q; // 2. 訪問済みフラグ設定. // ※スタート地点は, 距離ゼロを指定. memo[s] = 0; // 3. 探索地点 s をキュー q に追加. q.push(s); // 4. キュー q が 空になるまで, 探索. while(!q.empty()) { // 5. 頂点 u を キュー q から取り出す. int u = q.front(); q.pop(); // 6. 頂点 u が ゴールだったら終了. if(u == g) break; // 7. 取り出した要素を処理. for(auto &e : graph[u]){ // 7-1. 頂点u の 隣接する頂点e が, 未訪問だったら, キュー q に追加. if(memo[e] == 0 && e != s){ // 頂点e を キュー q に追加. q.push(e); // 頂点e に 距離memo[u] プラス 1 を 加算. memo[e] += memo[u]; memo[e]++; } } } } int main() { // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); // 2. グラフ作成. // 解説通り, グラフを3倍化？してみる. // 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を 張る. // 具体的には, // u0 = u, u1 = u + MAX_V, u2 = u + MAX_V * 2 // v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2 for(int i = 0; i < M * 3; i += 3){ int u, v; scanf("%d %d", &u, &v); u--, v--; // u0 -> v1 graph[u].push_back(v + MAX_V); // u1 -> v2 graph[u + MAX_V].push_back(v + MAX_V * 2); // u2 -> v0 graph[u + MAX_V * 2].push_back(v); } // 3. スタート地点, ゴール地点. int S, T; scanf("%d %d", &S, &T); S--, T--; // 4. S0 -> T0 の 最短距離 を 計算. bfs(S, T); // for(int i = 0; i < N * 3; i++) cout << memo[i] << " "; // cout << endl; // 5. 後処理. int ans = memo[T] / 3; if(ans == 0) printf("%d\n", -1); else printf("%d\n", ans); return 0; } |
■参照サイト
AtCoder Beginner Contest 132