C++の練習を兼ねて, AtCoder Grand Contest 013 の 問題C (Ants on a Circle) を解いてみた.
■感想.
1. 問題C は, 解答の方針が見えなかったので, 解説を参照して, 実装したところ, AC版に到達できた.
2. とはいえ, ゼッケン番号の増分, 減分 を 正しく計算するのに, 非常に苦労したように思う.
※ 具体的には, subtask_1_07.txt, subtask_1_09.txt, subtask_1_10.txt の WA回避部分.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 013 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/agc013/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, 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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; LL L, T; scanf("%d %lld %lld", &N, &L, &T); vector<P> v; LL w[N]; memset(w, 0, sizeof(w)); rep(i, N){ LL x; scanf("%lld %lld", &x, &w[i]); if(w[i] == 2) w[i] = -1; v.pb({x, i + 1}); // {現在の蟻の位置, 現在のゼッケン番号}. } // 2. 蟻(ゼッケン 1) の T秒後 の 状態. // -> 円周上 で 考える. LL count = 0; // ゼッケン番号の増分, 減分. int z1 = 1; // 蟻(ゼッケン 1) の T秒後 の ゼッケン番号. repx(i, 1, N){ // 向きが違う場合に, 評価. if(w[0] == 1 && w[i] == -1){ LL diff = v[i].a - v[0].a; if(diff <= 2 * T) count++; count += max(0LL, (2 * T - 1 - diff) / L); // subtask_1_07.txt の WA回避. } if(w[0] == -1 && w[i] == 1){ LL diff = L - v[i].a + v[0].a; if(diff <= 2 * T) count--; count -= max(0LL, (2 * T - diff) / L); // subtask_1_09.txt, subtask_1_10.txt の WA回避. } } // ゼッケン番号の増分, 減分を, mod N に 変換する必要あり. count %= N; z1 += (int)count; if(z1 <= 0) z1 += N; if(z1 > N) z1 -= N; // 3. 蟻 の T秒後 の 位置 を 円周上 に 変換. LL c = T / L + 1; // 周期. rep(i, N) v[i].a = (v[i].a + w[i] * T + L * c) % L; // 4. sort. sort(all(v)); // 5. ゼッケン付け替え. // -> もともと, ゼッケン 1 の 蟻が, ゼッケン Z に 変換されたので, // 他の蟻についても, ゼッケン番号 を 更新. // 5-1. 蟻(ゼッケン 1) の index. int idx = 0; rep(i, N){ if(v[i].b == 1){ idx = i; break; } } // 5-2. idx の 場合 を 更新. v[idx].b = z1; // 5-3. idx + 1 ～ N - 1 までを 更新. repx(i, idx + 1, N){ v[i].b = v[i - 1].b + 1; if(v[i].b > N) v[i].b -= N; } // 5-4. 0 ～ idx - 1 までを 更新. if(idx){ v[0].b = v[N - 1].b + 1; if(v[0].b > N) v[0].b -= N; } repx(i, 1, idx){ v[i].b = v[i - 1].b + 1; if(v[i].b > N) v[i].b -= N; } // 6. 出力. map<int, LL> m; // {T秒後のゼッケン番号, 蟻の位置(T秒後)}. rep(i, N) m[v[i].b] = v[i].a; for(auto &p : m) printf("%lld\n", p.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 |
[入力例] 3 8 3 0 1 3 2 6 1 [出力例] 1 3 0 ※AtCoderテストケースより [入力例] 4 20 9 7 2 9 1 12 1 18 1 [出力例] 7 18 18 1 ※AtCoderテストケースより [入力例] 7 77 777 0 2 18 1 31 1 37 1 42 2 55 2 76 1 [出力例] 38 44 48 70 6 25 35 [入力例] 31 415 9265 1 2 2 1 5 1 44 2 62 1 81 1 90 1 93 2 102 2 114 1 115 1 130 2 157 1 173 1 182 1 184 2 189 1 257 1 303 2 319 1 320 2 327 1 339 1 343 1 346 1 347 2 352 1 360 1 381 2 398 1 399 1 [出力例] 392 410 39 47 49 59 63 66 72 80 118 119 137 140 168 185 197 212 216 225 246 249 250 281 292 308 317 324 324 373 382 |
■参照サイト
AtCoder Grand Contest 013