C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題E (Amusement Park) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 216 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://atcoder.jp/contests/abc216/editorial/2469 // 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, b = 0, bSum = 0; scanf("%d %lld", &N, &K); rep(i, N){ scanf("%lld", &a[i]); b += a[i]; bSum += (a[i] + 1) * a[i] / 2; } // 2. 数列B の 項数が, K以下. if(b <= K){ printf("%lld\n", bSum); return 0; } // 3. 評価関数. auto f = [&](LL m) -> bool { // 3-1. 数列B で, m以上となる個数. LL ret = 0; rep(i, N) ret += max(a[i] - m + 1, 0LL); // 3-2. 判定結果. return (ret <= K); }; // 4. 二分探索で確認してみる. LL l = 1, h = 2e9 + 1, m; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%d l=%d m=%d\n", h, l, m); } // 5. 集計. LL t = 0, ans = 0; rep(i, N){ if(a[i] >= h){ ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計. t += (a[i] - h + 1); // 項数. } } // 6. 残り. if(t < K) ans += (h - 1) * (K - t); // 7. 出力. 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 |
[入力例] 3 5 100 50 102 [出力例] 502 ※AtCoderテストケースより [入力例] 2 2021 2 3 [出力例] 9 ※AtCoderテストケースより [入力例] 1 5 7 [出力例] 25 [入力例] 3 5 7 5 3 [出力例] 27 [入力例] 10 314 5 75 74 87 48 102 35 18 41 21 [出力例] 15734 [入力例] 20 2021 113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180 [出力例] 192343 [入力例] 50 20210910 5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659 [出力例] 82888537486520 |
■参照サイト
AtCoder Beginner Contest 216