C++の練習を兼ねて, AtCoder Beginner Contest 190 の 問題C (Bowls and Dishes) ～ 問題D (Staircase Sequences) を解いてみた.
■感想.
1. 久しぶりに, 解説見る前に, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 190 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) int a[101], b[101], x[101][2]; int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d", &N, &M); rep(i, M) scanf("%d %d", &a[i], &b[i]); scanf("%d", &K); rep(i, K) scanf("%d %d", &x[i][0], &x[i][1]); // 2. 全探索. int ans = 0; rep(i, 1 << K){ // 2-1. 皿C, D の置き方. // ex. // K = 5 で, i = 25 であれば, 11001 と見て, // 皿C には, 人1, 2, 5 が, 皿D には, 人3, 4 が ボールを置くと見る. int d[101]; rep(j, 101) d[j] = 0; rep(j, K){ int f = i & (1 << (K - 1 - j)); d[x[j][(f > 0)]]++; } // 2-2. 皿A, B の両方にボールが置かれているか を チェック. int t = 0; rep(j, M) if(d[a[j]] && d[b[j]]) t++; // 2-3. 最大値更新. ans = max(ans, t); } // 3. 出力. printf("%d\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 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 |
[入力例] 4 4 1 2 1 3 2 4 3 4 3 1 2 1 3 2 3 [出力例] 2 ※AtCoderテストケースより [入力例] 4 4 1 2 1 3 2 4 3 4 4 3 4 1 2 2 4 2 4 [出力例] 4 ※AtCoderテストケースより [入力例] 6 12 2 3 4 6 1 2 4 5 2 6 1 5 4 5 1 3 1 2 2 6 2 3 2 5 5 3 5 1 4 2 6 4 6 5 6 [出力例] 9 ※AtCoderテストケースより [入力例] 11 15 1 3 2 3 3 5 3 10 2 10 7 8 1 10 2 8 5 11 5 7 4 11 5 6 2 9 7 10 3 11 7 1 6 2 8 3 9 4 11 5 11 3 5 2 7 [出力例] 7 |
■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 |
// 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--) // 与えられた正の整数のすべての約数を抽出. // @param X: 約数を抽出したい正の整数. // @return ret: すべての約数(※1以上). set<LL> div(LL X){ set<LL> ret; ret.insert(1); for(LL d = 2; d * d <= X; d++){ if(X % d == 0){ ret.insert(d); if(d * d != X) ret.insert(X / d); } } ret.insert(X); return ret; } int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. すべての約数を抽出. set<LL> divisors = div(N); // 3. 約数が, 奇数のものの個数をカウント. int ans = 0; for(auto &d : divisors) if(d & 1) ans++; // 4. 出力. printf("%d\n", ans * 2); 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 |
[入力例] 12 [出力例] 4 ※AtCoderテストケースより [入力例] 1 [出力例] 2 ※AtCoderテストケースより [入力例] 963761198400 [出力例] 1920 ※AtCoderテストケースより [入力例] 202020212022 [出力例] 32 [入力例] 3736247840325 [出力例] 5184 [入力例] 12345678987654321 [出力例] 90 |
■参照サイト
AtCoder Beginner Contest 190