C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題B (01 Generation) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 実装に苦労したものの, 解説を参考に実装して, AC版に到達出来た.
2. 解説上 の 整数列S は, 配列インデックスが小さい順で, 見ていくものと仮定して, 実装している.
※配列インデックスが大きい順で見ていく場合は, 不正解になるように見える.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 138 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題B／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 |
// 解き直し. // https://atcoder.jp/contests/arc138/editorial/3743 // 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 pb push_back int main(){ // 1. 入力情報. int N, z = -1, one = 0; scanf("%d", &N); vi a(N); rep(i, N){ scanf("%d", &a[i]); // Filp. if(i & 1) a[i] ^= 1; // 1 の 個数. one += a[i]; // 先頭に最も近い 1 の場所は？ if(z == -1 && a[i]) z = i; } // 2. 01文字列作成(デバッグ用). // -> 操作 A, 操作 B を 適当に実行して, 01文字列 を 生成. auto g01 = [&](int n) -> string { string ret = ""; random_device seed; rep(i, n){ // 乱数. mt19937 engine(seed()); int r = engine() % 2; // 操作 A. if(r){ string t = "0"; rep(j, ret.size()) t.pb(((ret[j] - '0') ^ 1) + '0'); swap(t, ret); } // 操作 B. if(!r) ret.pb('0'); } return ret; }; // string s = g01(111); // printf("%s\n", s.c_str()); // 3. 例外(先頭 が, 0 でない). if(a[0]){ puts("No"); return 0; } // 4. 例外(Filp後 の 整数列 A が, すべて 0). if(!one){ puts("Yes"); return 0; } // 5. 部分列 S の 切り出し. deque<int> dq; repx(i, z, N) dq.pb(a[i]); // 6. 部分列 S の チェック. // -> 先頭から見ていき, 末尾(pos = (int)dq.size() - 1)まで到達できるか？. int zero = 0, pos = -1; bool ok = true; rep(i, (int)dq.size()){ // 終了条件. if(!ok) break; // 今回分設定. pos = i; int l = pos + zero; // 現在地点 が 0. if(!dq[i]){ // 長さが奇数だった. if(l & 1){ if(zero < z) ++zero; else ok = false; } } // 現在地点 が 1. if(dq[i]){ // 長さが偶数だった. if(!(l & 1)){ if(zero < z) ++zero; else ok = false; } } } // 7. 出力. printf("%s\n", (ok && (pos == (int)dq.size() - 1)) ? "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 |
[入力例] 4 0 1 1 0 [出力例] Yes ※AtCoderのテストケースより [入力例] 4 1 0 0 0 [出力例] No ※AtCoderのテストケースより [入力例] 4 0 0 0 1 [出力例] No ※AtCoderのテストケースより [入力例] 4 0 1 1 1 [出力例] Yes [入力例] 8 0 1 1 0 0 1 1 0 [出力例] No [入力例] 9 0 1 1 1 0 1 0 0 0 [出力例] No [入力例] 12 0 1 0 1 0 1 0 1 1 1 1 1 [出力例] Yes [入力例] 20 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 [出力例] Yes [入力例] 30 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 [出力例] No [入力例] 111 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 [出力例] Yes [入力例] 1234 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 [出力例] Yes |
■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)