C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題A (Candy Distribution Again) ~ 問題B (Garbage Collector) を解いてみた.
■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 解答に至るまでの実装方針が, 個人的には, 非常に不思議な印象を受ける面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 027 解説 を ご覧下さい.
■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 |
// 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]; int main(){ // 1. 入力情報. int N, x; scanf("%d %d", &N, &x); rep(i, N) scanf("%d", &a[i]); // 2. sort. sort(a, a + N); // 3. お菓子を配る. rep(i, N){ if(a[i] <= x) b[i] = a[i], x -= a[i]; else b[i] = x, x = 0; } if(x > 0) a[N - 1] += x; // 最終要素. // 4. 人数の最大値は? int ans = 0; rep(i, N) if(a[i] == b[i]) ans++; // 5. 出力. 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 |
[入力例] 3 70 20 30 10 [出力例] 2 ※AtCoderのテストケースより [入力例] 3 10 20 30 10 [出力例] 1 ※AtCoderのテストケースより [入力例] 4 1111 1 10 100 1000 [出力例] 4 ※AtCoderのテストケースより [入力例] 2 10 20 20 [出力例] 0 ※AtCoderのテストケースより [入力例] 5 123 15 31 67 32 84 [出力例] 3 |
■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 |
// 解き直し. // https://img.atcoder.jp/agc027/editorial.pdf // 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 x[202020], xCum[202020]; int main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); rep(i, N) scanf("%d", &x[i]); // 2. 累積和. rep(i, N) xCum[i + 1] = xCum[i] + x[i]; // 3. 必要なエネルギーの最小値を計算. LL ans = 202020202020202020; repx(k, 1, N + 1){ LL cur = 0; repex(s, 1, N + 1, k){ // 3-1. E(i, x) を 計算. int i = s / k; if(s % k != 0) i++; int g = min(N, s + k - 1); // 3-2. k に対するエネルギーを計算. int ns = N - g, ng = N - s + 1; if(i == 1) cur += 5 * (xCum[ng] - xCum[ns]); else cur += (LL)(2 * i + 1) * (xCum[ng] - xCum[ns]); } // 3-3. 最小値更新. // -> test_13.txt, test_14.txt の Overflow対策. LL diff = (LL)(N + k) * X; if(ans - cur > diff) ans = cur + diff; } // 4. 出力. 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
[入力例] 2 100 1 10 [出力例] 355 ※AtCoderのテストケースより [入力例] 5 1 1 999999997 999999998 999999999 1000000000 [出力例] 19999999983 ※AtCoderのテストケースより [入力例] 10 8851025 38 87 668 3175 22601 65499 90236 790604 4290609 4894746 [出力例] 150710136 ※AtCoderのテストケースより [入力例] 16 10 1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408 [出力例] 3256017715 ※AtCoderのテストケースより [入力例] 3 14 15 9 26 [出力例] 320 [入力例] 25 47 1 5 11 20 23 24 30 41 42 43 46 55 59 68 74 87 90 92 101 105 115 120 124 137 142 [出力例] 10001 [入力例] 50 20210421 471016 997883 1801666 2830430 3345391 3447316 3702870 4755430 5061374 5880249 6034233 7136353 7448252 8342289 9089895 10138757 10688060 10859188 11516771 12205763 12313002 13266027 14088442 15145933 16347096 17568780 18572974 19696877 20818373 21063001 21212244 21610377 21667308 21763666 21828525 23057695 23862364 24786068 25097793 26064195 27246200 27953738 29139100 30229038 30841882 31533903 31968519 32828786 34016064 35155115 [出力例] 5660125250 |
■参照サイト
AtCoder Grand Contest 027