C++の練習を兼ねて, AtCoder Regular Contest 154 の 問題C (Roller) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 解説のロジックで, 正整数列 A を 正整数列 B が 一致させることが出来るかどうかを判定できる点が, 非常に面白く感じた.
3. 実装上で, 判断に迷った箇所としては, rotate で, 正整数列 A と比較する対象が, 正整数列 B ではなく, 圧縮後 の 正整数列 B という点に, 少し注意が必要と感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 154 解説 の 各リンク を ご覧下さい.
■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://atcoder.jp/contests/arc154/editorial/5548 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 pub push_back #define pob pop_back int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. テストケース. rep(i, T){ // 2-1. 各テストケース. int N; scanf("%d", &N); vi A(N), B(N), ExA(N * 2); rep(j, N){ scanf("%d", &A[j]); ExA[j] = ExA[j + N] = A[j]; } rep(j, N) scanf("%d", &B[j]); // 2-2. A = B の 場合(操作回数ゼロ). if(A == B){ puts("Yes"); continue; } // 2-3. 数列 B 圧縮(操作回数ゼロでない). // -> 以下のようなパターンで, WA版となるため, ロジック修正. // ex. // 5 // 2 1 2 1 2 // 1 2 1 2 1 // -> このケースは, 正整数列 B は, X = (1, 2, 1, 2), Y = (2, 1, 1, 1) に 圧縮され, // 圧縮後の長さが, X = (1, 2, 1, 2) の 4 であるため, Yes の 候補となる. // 結論は, Yes. // // ex. // 7 // 1 2 3 2 1 2 3 // 3 2 1 2 3 2 1 // -> このケースは, 正整数列 B は, X = (3, 2, 1, 2, 3, 2, 1), Y = (1, 1, 1, 1, 1, 1, 1) に 圧縮され, // 圧縮後の長さが, X = (3, 2, 1, 2, 3, 2, 1) の 7 (= N) であるため, No. // // ex. // 10 // 3 1 4 1 5 9 2 6 5 3 // 1 1 4 1 5 2 2 5 1 1 // -> このケースは, 正整数列 B は, X = (1, 4, 1, 5, 2, 5), Y = (4, 1, 1, 1, 2, 1) に 圧縮され, // 圧縮後の長さが, X = (1, 4, 1, 5, 2, 5) の 6 であるため, Yes の 候補となる. // 結論は, Yes. vi C; C.pub(B[0]); repx(j, 1, N) if(C.back() != B[j]) C.pub(B[j]); if(C.size() > 1 && C.front() == C.back()) C.pob(); // 2-4. 正整数列 B を 圧縮したときに, N である場合. if(C.size() == N){ puts("No"); continue; } // 2-5. 貪欲法. int x = 0; rep(a, N){ // 初期化. x = 0; int idx = a; // 数列 A の 区間[a, a + N - 1] で 数列 C と 比較. for(auto &c : C){ repx(j, idx, a + N){ if(ExA[j] == c){ ++x; idx = j; break; } } } // ある単調増加整数列が, 見つかった. if(x == C.size()) break; } // 2-6. 出力. printf("%s\n", (x == C.size()) ? "Yes" : "No"); } 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 |
[入力例] 3 2 1 2 2 2 4 2 3 1 1 2 1 1 2 2 1 1 2 2 [出力例] Yes Yes No ※AtCoderのテストケースより [入力例] 3 5 1 2 3 4 5 1 2 3 5 5 10 3 1 4 1 5 9 2 6 5 3 1 1 4 1 5 2 2 5 1 1 9 1 2 3 1 2 3 1 2 3 3 1 2 3 1 2 3 1 2 [出力例] Yes Yes No [入力例] 5 1 1 1 2 2 1 2 2 3 3 2 2 3 1 2 4 1 2 3 4 1 3 1 3 5 5 4 3 2 1 3 2 1 1 1 [出力例] Yes Yes No No Yes [入力例] 3 12 10 6 1 1 4 5 3 2 5 6 5 9 1 1 1 1 5 5 2 2 5 6 9 9 15 5 8 1 10 8 6 7 2 8 10 1 6 3 10 9 5 8 8 8 6 6 7 7 8 10 1 6 10 10 5 20 5 18 12 17 19 15 6 13 1 8 15 11 12 18 1 7 11 20 20 11 5 12 12 15 15 15 1 1 1 8 15 12 12 18 1 11 11 11 11 11 [出力例] Yes Yes Yes [入力例] 3 50 22 1 29 32 26 17 39 47 34 7 7 7 13 21 16 40 50 16 8 37 16 27 38 50 43 11 28 21 32 29 15 39 26 23 33 15 37 4 22 23 5 20 4 17 28 32 34 5 47 46 1 1 29 32 17 17 39 47 34 7 7 13 13 21 50 50 50 16 8 37 16 50 50 50 43 11 28 21 15 15 33 33 33 33 33 15 37 22 22 23 20 20 4 17 28 32 34 5 47 1 30 21 9 29 23 13 10 15 1 2 17 12 27 27 27 17 4 21 7 24 30 28 7 17 19 2 29 1 8 14 9 21 10 10 23 10 10 15 1 2 17 12 10 27 27 17 21 21 24 24 28 28 17 2 2 2 1 1 8 14 9 120 27 1 64 44 46 65 62 31 30 50 40 48 13 14 34 76 29 55 17 22 44 77 27 42 72 10 24 35 35 8 25 68 63 13 4 28 34 14 50 40 60 25 72 54 2 5 68 47 63 72 61 51 30 69 9 22 24 32 75 19 8 47 42 32 46 32 11 76 34 39 67 25 39 58 77 27 69 3 49 17 15 5 30 36 66 44 46 58 6 58 46 9 61 55 11 5 38 10 54 39 22 16 45 22 19 10 39 80 15 56 54 30 42 1 2 21 7 42 73 77 1 1 64 50 50 50 50 50 50 50 40 48 13 14 34 76 29 55 17 22 77 77 72 72 72 10 24 35 8 8 25 68 63 13 50 50 50 50 50 40 60 5 5 5 5 5 63 63 63 61 61 51 30 69 9 22 24 75 75 19 8 11 11 11 11 11 11 39 39 39 77 77 77 77 77 3 3 3 17 17 5 5 30 36 66 6 6 6 6 11 11 11 11 11 11 5 10 10 54 39 22 16 22 22 19 10 80 80 15 56 54 1 1 1 2 7 7 77 77 77 [出力例] Yes No Yes [入力例] 2 5 2 1 2 1 2 1 2 1 2 1 7 1 2 3 2 1 2 3 3 2 1 2 3 2 1 [出力例] Yes No |
■参照サイト
AtCoder Regular Contest 154