C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題C (Many Balls) ~ 問題D (Pair of Balls) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D で, 計算量を減らすための, キューの利用方法が, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 216 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 魔法を使ってみる. string ans = ""; while(N){ ans = ((N % 2 > 0) ? "A" : "B") + ans; if(N % 2 > 0) N--; else N >>= 1; } // 3. 出力. printf("%s\n", ans.c_str()); 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 |
[入力例] 5 [出力例] AABA ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. ABBA [入力例] 14 [出力例] BBABBAAAB ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. ABABAB [入力例] 2021 [出力例] ABABABABABABBBABBA [入力例] 20210909 [出力例] ABBBABABBABBBBABABBBABBBABABBABABABBA [入力例] 999999999999999999 [出力例] ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA [入力例] 1000000000000000000 [出力例] ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc216/editorial/2559 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 pof pop_front #define pub push_back int c[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vector<deque<int>> v(M), b(N); rep(i, M){ int k; scanf("%d", &k); rep(j, k){ int a; scanf("%d", &a); a--; v[i].pub(a); // i番目の筒に保存. b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存. } } // 2. 筒を順番に見ていく. deque<int> dq; rep(i, M){ // 2-1. ボールを取得. int t = v[i].front(); c[t]++; // 2-2. キューに追加. if(c[t] == 2) dq.pub(t); // 2-3. キューが空になるまで, 筒からボールを取り除く. while(!dq.empty()){ // ボールを取得. int u = dq.front(); dq.pof(); // 筒番号を取得. int p1 = b[u].front(); b[u].pof(); int p2 = b[u].front(); b[u].pof(); // 筒から除去. v[p1].pof(); v[p2].pof(); // 筒から, 一番上のボールを取得. int b1 = -1; int b2 = -1; if(!v[p1].empty()) b1 = v[p1].front(); if(!v[p2].empty()) b2 = v[p2].front(); // 取得したボールの出現回数を確認し, 二回であれば, キューに追加. if(b1 != -1){ c[b1]++; if(c[b1] == 2) dq.pub(b1); } if(b2 != -1){ c[b2]++; if(c[b2] == 2) dq.pub(b2); } } } // 3. 判定. bool ok = true; rep(i, N) if(c[i] != 2) ok = false; // 4. 出力. printf("%s\n", ok ? "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 |
[入力例] 2 2 2 1 2 2 1 2 [出力例] Yes ※AtCoderテストケースより [入力例] 2 2 2 1 2 2 2 1 [出力例] No ※AtCoderテストケースより [入力例] 10 6 4 9 4 2 1 5 10 9 8 4 2 3 5 3 1 4 8 6 5 3 2 7 6 2 10 7 [出力例] Yes [入力例] 3 3 2 2 1 2 3 2 2 1 3 [出力例] No [入力例] 25 10 3 17 9 1 4 22 9 6 2 8 25 23 17 16 14 10 5 1 5 24 20 16 8 2 5 18 14 11 6 3 7 19 18 15 10 8 3 4 9 24 22 19 15 13 12 11 7 4 4 23 20 12 5 3 21 13 7 2 25 21 [出力例] Yes |
■参照サイト
AtCoder Beginner Contest 216