C++の練習を兼ねて, AtCoder Regular Contest 149 の 問題D (Simultaneous Sugoroku) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 実装に非常に苦労したものの, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 個人的には, 解説のロジックで, 最終状態の各コマの座標が分かるという点が, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 149 解説 の 各リンク を ご覧下さい.
■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 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 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 |
// 解き直し. // https://atcoder.jp/contests/arc149/editorial/4902 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; using vi = vector<int>; using vvi = vector<vi>; #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 X[303030], D[303030]; P g[1010101]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%d", &X[i]); rep(i, M) scanf("%d", &D[i]); int n = X[N - 1] + 1; // 2. コマの移動. // -> ロジック修正(04_small_d_01.txt などの WA を 回避するため). LL m = 0; P nCur = {1, X[N - 1]}; // 数字 {左端, 右端}. P pCur = {1, X[N - 1]}; // 座標 {左端, 右端}. rep(i, M){ // 終了条件. if(nCur.a == nCur.b && g[nCur.a].a) break; // チェック. assert(nCur.a <= nCur.b); assert(pCur.a <= pCur.b); // 移動先候補. P pNex = {pCur.a, pCur.b}; // 移動方向 が 負. if(pCur.a > 0){ pNex.a -= D[i]; pNex.b -= D[i]; m -= D[i]; } // 移動方向 が 正. if(pCur.b < 0){ pNex.a += D[i]; pNex.b += D[i]; m += D[i]; } // ゼロを含む. if(pNex.a * pNex.b == 0){ // 両端がゼロ. if(pNex.a == 0 && pNex.b == 0){ // 0 の 位置. int z = (int)(nCur.b); // コマが原点に到達した. g[z].a = i + 1; // 終了. break; } // 左端がゼロ. if(pNex.a == 0){ // 0 の 位置. int z = (int)(nCur.a); // コマが原点に到達した. g[z].a = i + 1; // 更新. nCur.a = z + 1; // 左端 の 数字. pCur.a = 1; // 左端 の 座標. pCur.b = pNex.b; // 右端 の 座標. } // 右端がゼロ. if(pNex.b == 0){ // 0 の 位置. int z = (int)(nCur.b); // コマが原点に到達した. g[z].a = i + 1; // 更新. nCur.b = z - 1; // 右端 の 数字. pCur.b = -1; // 右端 の 座標. pCur.a = pNex.a; // 左端 の 座標. } // 次へ. continue; } // 符号が異なる. if(pNex.a * pNex.b < 0){ // 左側, 右側 の 長さ. int l = (int)abs(pNex.a); int r = (int)abs(pNex.b); // 左側 >= 右側. if(l >= r){ // 0 の 位置. int z = (int)(nCur.b - r); // コマが原点に到達した. g[z].a = i + 1; // それ以外のコマ. rep(j, r) g[z + (j + 1)].b = z - (j + 1); // 更新. nCur.b = z - 1; // 右端 の 数字. pCur.b = -1; // 右端 の 座標. pCur.a = pNex.a; // 左端 の 座標. } // 左側 < 右側. if(l < r){ // 0 の 位置. int z = (int)(nCur.a + l); // コマが原点に到達した. g[z].a = i + 1; // それ以外のコマ. rep(j, l) g[z - (j + 1)].b = z + (j + 1); // 更新. nCur.a = z + 1; // 左端 の 数字. pCur.a = 1; // 左端 の 座標. pCur.b = pNex.b; // 右端 の 座標. } } // 符号が同じ. if(pNex.a * pNex.b > 0) pCur = pNex; } // 3. グラフ作成. vvi G(n); repx(i, 1, n){ // コマが原点に到達した. if(g[i].a) continue; // コマが原点に到達しなかった. if(!g[i].b) continue; // それ以外. G[i].pb(g[i].b); G[g[i].b].pb(i); } // 4. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, vp &p, int s, int* d){ // 空のキュー. queue<int> q; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 隣接頂点をチェック. for(auto &v : G[u]){ if(!d[v] && v != s){ d[v] = d[u] + 1; q.push(v); // 根であるコマが原点に到達した. if(g[s].a){ p[v].a = p[s].a; p[v].b = p[s].b; continue; } // 根であるコマが原点に到達しなかった. p[v].a = p[s].a * ((d[v] & 1) ? (-1) : 1); p[v].b = p[s].b; } } } }; // 5. 各コマ情報の更新. // -> 根は, コマが原点に到達した or 到達しなかったものとして, bfs. int d[n]; vp ans(n); repx(i, 1, n){ ans[i].a = 0; ans[i].b = 0; d[i] = 0; if(!g[i].b){ // 根であるコマが原点に到達した. if(g[i].a){ ans[i].a = g[i].a; ans[i].b = 1; continue; } // 根であるコマが原点に到達しなかった. ans[i].a = i + m; ans[i].b = 0; } } repx(i, 1, n) if(!g[i].b && !d[i]) bfs(G, ans, i, d); // 6. 出力. rep(i, N) printf("%s %lld\n", ans[X[i]].b ? "Yes" : "No", ans[X[i]].a); 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 |
[入力例] 6 4 2 4 6 8 10 12 8 2 5 7 [出力例] No -6 No -4 Yes 2 Yes 1 Yes 2 No 4 ※AtCoderテストケースより [入力例] 3 3 1 2 3 1 1 1 [出力例] Yes 1 Yes 2 Yes 3 [入力例] 3 3 1 2 3 2 2 2 [出力例] No -1 Yes 1 No 1 [入力例] 7 5 1 3 5 6 8 9 10 1 2 3 2 1 [出力例] Yes 1 Yes 2 Yes 5 Yes 3 Yes 4 Yes 5 No 1 [入力例] 10 7 1 2 3 4 5 6 7 8 9 10 3 1 4 1 5 9 2 [出力例] No 4 Yes 2 Yes 1 Yes 2 No -4 No -3 Yes 4 Yes 3 Yes 4 No 3 [入力例] 12 10 1 2 3 7 9 10 12 13 15 16 19 20 9 6 3 4 8 2 1 5 7 10 [出力例] No -6 No -5 Yes 2 No -6 Yes 1 No 5 Yes 3 No -6 Yes 2 No 5 No -6 No -5 [入力例] 30 30 6 9 10 11 13 14 19 21 23 26 28 29 34 36 41 45 47 49 52 55 58 61 66 68 73 77 81 83 84 87 22 3 60 6 7 9 77 4 9 9 78 96 9 6 40 91 7 36 68 73 12 7 6 23 5 4 40 6 18 3 [出力例] No -12 Yes 25 No 10 No 11 Yes 26 No -12 Yes 2 No 9 No -9 No 8 No 10 No 11 No -10 No 10 Yes 26 Yes 15 No 11 Yes 26 No -12 Yes 25 No 12 No -11 No 12 No -12 Yes 25 Yes 26 Yes 26 No -11 No -10 No 11 |
■参照サイト
AtCoder Regular Contest 149