C++の練習を兼ねて, AtCoder Grand Contest 018 の 問題A (Getting Difference) ～ 問題B (Sports Festival) を解いてみた.
■感想.
1. 問題B は, 解答方針が見えなかったので, 解説を参照して実装したところ, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 018 解説 を ご覧下さい.
■C++版プログラム(問題A／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 |
// 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 a[101010]; int main(){ // 1. 入力情報. int N; LL K; scanf("%d %lld", &N, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 最大公約数を計算. LL g = a[0]; repx(i, 1, N) g = __gcd(g, a[i]); // 3. 判定. // -> K以上で, 差分が, 最大公約数 の 倍数 となるものがあるか？ bool ok = false; rep(i, N){ if(a[i] >= K && (a[i] - K) % g == 0){ ok = true; break; } } // 4. 出力. printf("%s\n", ok ? "POSSIBLE" : "IMPOSSIBLE"); 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 |
[入力例] 3 7 9 3 4 [出力例] POSSIBLE ※AtCoderテストケースより [入力例] 3 5 6 9 3 [出力例] IMPOSSIBLE ※AtCoderテストケースより [入力例] 4 11 11 3 7 15 [出力例] POSSIBLE ※AtCoderテストケースより [入力例] 5 12 10 2 8 6 4 [出力例] IMPOSSIBLE ※AtCoderテストケースより [入力例] 30 12920 13889 3689 12886 19397 16456 4301 4471 16864 18700 11781 12393 10829 4981 12410 13753 9197 19091 3791 7718 3366 14161 6069 6868 4726 7939 11815 4318 20757 16116 4862 [出力例] POSSIBLE |
■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 |
// 解き直し. // https://img.atcoder.jp/agc018/editorial.pdf // 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[303][303], P[303], Q[303]; // 入力情報, シミュレーション済のスポーツ, 各スポーツの参加人数. int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) rep(j, M) scanf("%d", &a[i][j]); // 2. シミュレーションを実施. int ans = 2020202020; auto dfs = [&](auto&& self, int d) -> void{ // 2-1. 終了条件. if(d == 0) return; // 2-2. 初期化. memset(Q, 0, sizeof(Q)); // 2-3. 各選手について, どのスポーツに参加するか確認. rep(i, N){ rep(j, M){ // 2-4. スポーツを取得. int p = a[i][j]; // 2-5. 未選択のスポーツの場合. // -> 一番お気に入り順位の高いものだけを選択. if(!P[p]){ Q[p]++; break; } } } // 2-6. 最大値更新. int curQ = 0, curP = -1; repx(p, 1, M + 1){ if(!P[p] && curQ < Q[p]){ curQ = Q[p]; // 参加人数. curP = p; // スポーツ. } } // 2-7. 今回のシミュレーション結果を反映. ans = min(ans, curQ); P[curP]++; // 2-8. 次の処理へ. self(self, --d); }; dfs(dfs, M); // 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 85 86 87 88 89 90 |
[入力例] 4 5 5 1 3 4 2 2 5 3 1 4 2 3 1 4 5 2 5 4 3 1 [出力例] 2 ※AtCoderテストケースより [入力例] 3 3 2 1 3 2 1 3 2 1 3 [出力例] 3 ※AtCoderテストケースより [入力例] 7 10 1 2 3 4 5 6 7 8 9 10 3 1 5 6 2 4 9 8 7 10 3 5 10 2 4 1 8 7 6 9 3 5 7 6 4 8 1 10 9 2 5 3 7 4 10 2 6 8 9 1 5 7 6 9 10 8 4 1 3 2 1 5 7 3 10 6 9 4 2 8 [出力例] 2 [入力例] 10 15 11 8 5 7 12 6 2 4 3 13 14 9 15 1 10 13 3 8 11 10 9 5 15 6 1 12 2 14 7 4 3 8 7 2 13 4 10 14 15 6 11 9 5 1 12 8 6 14 4 12 15 13 3 5 1 9 7 10 2 11 8 5 7 14 1 13 4 3 6 9 12 10 15 11 2 3 8 7 14 6 11 9 1 12 15 13 5 10 4 2 7 8 5 1 11 13 6 15 10 3 9 2 12 14 4 3 8 5 14 6 4 9 13 12 11 10 15 7 1 2 5 8 1 2 6 12 15 11 3 14 7 10 4 13 9 3 7 8 13 6 4 9 10 2 1 14 11 15 5 12 [出力例] 3 [入力例] 35 20 3 8 13 2 10 14 11 7 18 15 20 6 17 5 16 19 12 9 1 4 17 20 2 3 13 1 9 7 18 16 12 10 8 4 11 15 19 5 14 6 3 4 14 13 18 9 5 10 12 19 1 11 17 16 20 15 8 2 6 7 8 18 1 19 5 12 13 7 20 2 16 10 11 17 9 3 6 14 4 15 1 12 14 11 10 5 16 19 18 6 13 8 7 2 9 4 17 3 15 20 18 13 11 2 12 20 4 1 14 16 7 15 19 3 17 5 9 10 6 8 3 17 12 6 11 19 15 1 16 2 13 20 9 8 10 14 4 7 18 5 1 11 14 8 15 3 19 10 6 18 5 4 7 13 20 2 17 9 12 16 16 14 6 3 2 13 19 9 5 7 12 17 8 10 11 18 1 15 20 4 14 4 17 11 2 10 18 3 15 19 1 6 5 9 16 8 13 7 20 12 11 2 6 7 15 19 4 20 13 9 18 14 17 5 3 10 8 12 16 1 18 6 2 7 1 13 15 12 5 16 3 17 14 9 11 10 8 19 20 4 17 18 19 2 15 13 1 14 5 6 4 9 12 16 7 3 20 10 11 8 4 11 5 8 14 7 12 17 1 20 6 19 10 2 9 13 18 3 16 15 19 5 14 9 8 10 18 4 13 17 2 11 20 12 6 1 7 15 3 16 3 14 12 19 5 2 10 4 8 7 9 15 16 1 13 20 6 11 17 18 20 17 8 13 1 9 11 3 18 6 19 14 16 4 10 12 7 2 5 15 3 13 19 2 16 18 4 8 12 6 5 10 17 20 11 7 9 14 1 15 2 4 17 10 16 20 15 1 13 3 7 12 14 11 9 19 18 5 6 8 4 15 20 8 14 9 11 17 16 7 13 3 10 12 2 19 5 6 1 18 14 3 7 13 19 18 16 9 12 15 8 11 20 1 4 6 10 5 2 17 5 2 15 9 10 12 14 13 3 11 4 20 7 19 1 6 17 8 18 16 8 3 18 4 7 17 5 10 14 11 12 1 15 2 6 13 20 16 9 19 5 18 15 10 12 13 7 11 20 16 1 4 17 14 6 8 19 9 3 2 13 16 7 2 10 5 14 1 6 15 18 19 20 11 3 9 8 17 4 12 4 1 8 12 19 6 7 5 13 9 2 18 11 14 17 15 10 20 16 3 14 2 17 8 13 1 18 4 11 15 5 7 16 12 9 3 19 10 20 6 8 4 1 6 12 17 3 9 18 11 2 7 15 20 5 10 13 16 19 14 8 10 15 13 18 20 1 9 3 11 17 5 6 7 16 14 4 2 19 12 9 7 12 3 18 2 6 8 10 14 19 1 17 11 5 15 20 16 13 4 5 8 20 9 11 14 6 4 1 15 2 18 3 7 16 12 13 10 17 19 17 15 18 9 14 1 13 7 19 3 16 12 11 10 2 20 4 6 5 8 13 7 4 15 2 6 17 14 20 3 12 16 8 18 9 5 10 11 1 19 4 14 10 6 5 11 8 18 20 2 12 15 3 13 9 17 1 16 7 19 7 8 12 16 19 18 9 17 1 3 6 5 15 14 2 20 10 11 4 13 [出力例] 5 |
■参照サイト
AtCoder Grand Contest 018