C++の練習を兼ねて, AtCoder Beginner Contest 200 の 問題C (Ringo’s Favorite Numbers 2) ～ 問題D (Happy Birthday! 2) を解いてみた.
■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 200 解説 を ご覧下さい.
■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 |
// 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--) LL b[202]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ int a; scanf("%d", &a); a %= 200; b[a]++; } // 2. 条件を満たす整数の個数を計算. LL ans = 0; rep(i, 200) if(b[i]) ans += (b[i] - 1) * b[i] / 2; // 3. 出力. printf("%lld\n", ans); 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 |
[入力例] 6 123 223 123 523 200 2000 [出力例] 4 ※AtCoderテストケースより [入力例] 5 1 2 3 4 5 [出力例] 0 ※AtCoderテストケースより [入力例] 8 199 100 200 400 300 500 600 200 [出力例] 9 ※AtCoderテストケースより [入力例] 50 15 10 11 5 10 7 2 13 13 20 6 2 4 14 2 1 4 16 5 13 10 5 11 16 5 8 7 1 12 4 6 16 6 7 4 3 1 15 1 13 9 6 7 5 12 5 30 20 6 2 [出力例] 65 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc200/editorial/1246 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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[202], memo[202]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%d", &a[i]); a[i] %= 200; } // 2. 探索を行う. int u = min(N, 8), lb = 0, lc = 0; vvi D(202); vi B, C; bool ok = false; rep(i, 1 << u){ // 2-1. 初期化. B.clear(); // 2-2. 数列 B を, i の bit が 1 と見做して保存. rep(j, u) if(i & (1 << (u - 1 - j))) B.pb(j); // 2-3. 数列 B について, 和を計算. lb = B.size(); int bSum = 0; if(lb == 0) continue; rep(j, lb) bSum += a[B[j]]; bSum %= 200; // 2-4. 二回目出現パターンか確認. if(memo[bSum]){ ok = true; C = D[bSum]; lc = C.size(); break; } // 2-5. 数列の保存など. memo[bSum]++; D[bSum] = B; } // 3. 出力. if(ok){ puts("Yes"); printf("%d ", lb); rep(i, lb){ printf("%d", B[i] + 1); printf("%s", (i < lb - 1) ? " " : "\n"); } printf("%d ", lc); rep(i, lc){ printf("%d", C[i] + 1); printf("%s", (i < lc - 1) ? " " : "\n"); } }else{ puts("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 |
[入力例] 5 180 186 189 191 218 [出力例] Yes 1 1 2 3 4 ※AtCoderテストケースより [入力例] 2 123 523 [出力例] Yes 1 1 1 2 ※AtCoderテストケースより [入力例] 6 2013 1012 2765 2021 508 6971 [出力例] No ※AtCoderテストケースより [入力例] 20 539 476 114 457 693 610 624 703 255 989 64 193 1034 400 303 745 1141 8 1178 981 [出力例] Yes 2 5 6 1 8 ※ 実際, A5 + A6 = 693 + 610 = 1303, A8 = 703 となり, 200 で割った余りが等しい. [入力例] 25 325 3753 8849 7696 2933 11238 517 11809 10209 6511 7962 1041 2041 8832 3662 2965 2129 1003 11291 7125 431 11666 11999 990 10996 [出力例] Yes 3 4 5 8 1 6 ※ 実際, A4 + A5 + A8 = 7696 + 2933 + 11809 = 22438, A6 = 11238 となり, 200 で割った余りが等しい. |