C++の練習を兼ねて, AtCoder Regular Contest 126 の 問題C (Maximize GCD) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 操作後の最大値を計算できることに, 非常に興味深い印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 126 解説 の 各リンク を ご覧下さい.
■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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// 解き直し. // https://atcoder.jp/contests/arc126/editorial/2635 // 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 a[303030]; LL c[606060], s[606060]; int main(){ // 1. 入力情報. int N, aMax = 0; LL K; scanf("%d %lld", &N, &K); rep(i, N){ scanf("%d", &a[i]); aMax = max(aMax, a[i]); ++c[a[i]]; s[a[i]] += (LL)a[i]; } // 2. 累積和. rep(i, aMax * 2){ s[i + 1] += s[i]; c[i + 1] += c[i]; } // 3. cost(x). LL ans = 0; repx(x, 1, aMax + 1){ // 3-1. x の 倍数にするために必要な操作回数. LL op = 0; // 3-2. k の 上限. int kMax = aMax / x + ((aMax % x) > 0); repx(k, 1, kMax + 1){ // 解説上に記載されている k * x * c - s の 計算. int r = k * x; int l = (k - 1) * x; op += k * x * (c[r] - c[l]) - (s[r] - s[l]); } // 3-3. 最大値更新. if(op <= K) ans = max(ans, (LL)x); } // 4. x > aMax. LL y = (K + s[aMax]) / (LL)N; if(y > (LL)aMax) ans = max(ans, y); // 5. 出力. 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 |
[入力例] 3 6 3 4 9 [出力例] 5 ※AtCoderのテストケースより [入力例] 3 4 30 10 20 [出力例] 10 ※AtCoderのテストケースより [入力例] 5 12345 1 2 3 4 5 [出力例] 2472 ※AtCoderのテストケースより [入力例] 7 12 3 1 4 1 5 9 2 [出力例] 3 [入力例] 20 100 76 37 41 50 123 24 9 20 61 8 111 121 72 112 86 36 117 70 51 55 [出力例] 13 [入力例] 50 2022 99 64 74 87 90 81 57 14 59 10 71 74 81 10 26 57 99 30 7 101 102 58 121 118 102 5 78 74 55 18 112 85 74 37 109 112 49 3 18 100 67 55 28 50 93 85 81 116 122 73 [出力例] 75 [入力例] 100 20220607 3884 4387 31206 34567 30467 7730 12541 20631 5592 17213 15420 111 11550 17721 4442 16553 27015 16988 18479 15529 18142 16303 8626 30524 16723 2598 26485 28292 9613 16874 25869 30508 9667 17443 1214 4692 28455 18285 16191 18791 4031 16178 12238 22222 20362 21558 27707 3961 7103 8346 26037 1205 30867 19156 806 27366 13291 16768 9366 3908 21931 5649 980 7743 10574 23456 12345 32145 5075 931 10312 13317 11260 21399 14398 10319 11983 8833 4212 30249 8072 5908 1583 7312 12140 25860 4076 1239 24414 3716 33300 23456 13347 25872 7858 954 2292 782 17718 12628 [出力例] 216600 |
■参照サイト
AtCoder Regular Contest 126