C++の練習を兼ねて, AtCoder Beginner Contest 134 の 問題D (Preparing Boxes) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 個人的には, 大きい数が書かれた箱から処理していくというロジックが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 134 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc134/editorial.pdf // 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 a[202020], b[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i + 1]); // 2. 大きい数が書かれた箱から, ボールを入れていく. vi ans; repr(i, N, 1){ // i の 倍数が書かれた箱について, ボールが合計いくつ入っているか数える. int c = 0; repex(j, i, N + 1, i) c += b[j]; // 偶奇が異なる場合に, ボールを追加. if((c + a[i]) & 1){ b[i] += 1; ans.pb(i); } } // 3. 出力. int n = ans.size(); printf("%d\n", n); rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n"); 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 |
[入力例] 3 1 0 0 [出力例] 1 1 ※AtCoderテストケースより [入力例] 5 0 0 0 0 0 [出力例] 0 ※AtCoderテストケースより [入力例] 7 1 0 1 0 1 0 1 [出力例] 3 7 5 3 [入力例] 30 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 [出力例] 12 29 27 26 25 23 22 20 16 15 11 10 3 [入力例] 100 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 [出力例] 48 100 98 97 94 93 90 87 86 85 84 83 80 79 76 75 74 72 71 68 64 62 60 57 56 55 51 50 47 46 44 40 39 38 37 35 31 30 28 25 24 23 19 17 14 10 9 6 3 |
■参照サイト
AtCoder Beginner Contest 134