C++の練習を兼ねて, AtCoder Regular Contest 021 の 問題C (増築王高橋君) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 二分探索(応用版, 桁数オーバーフロー注意)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 021 解説 を ご覧下さい.
■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 61 62 63 64 65 |
// 解き直し. // https://www.slideshare.net/chokudai/arc021 // 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], d[101010]; int main(){ // 1. 入力情報. int N; LL K; scanf("%lld %d", &K, &N); rep(i, N) scanf("%lld %lld", &a[i], &d[i]); // 2. 評価関数. auto f = [&](LL m) -> bool { // 2-1. 最後に選んだ増築費用を, m として, 合計 K 回 以上に出来るか？ LL k = 0; rep(i, N) if(m >= a[i]) k += (m - a[i] + d[i]) / d[i]; // 2-2. 判定結果. return (k >= K); }; // 3. 二分探索で確認してみる. // -> 関数 f 内での オーバーフロー注意？ LL l = 0, h = 2e12 + 1; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4. 集計. LL ans = 0; rep(i, N){ if(h >= a[i]){ // 建物 i の 増築回数. LL q = (h - a[i] + d[i]) / d[i]; // 増築価格更新. // -> オーバーフロー注意？ ans += (a[i] * q) + (q - 1) * q / 2 * d[i]; // 増築回数 の 減算. K -= q; } } // 5. 残分. // -> K が マイナスのケースも考慮. ans += h * K; // 6. 出力. 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 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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
[入力例] 4 3 10 3 12 4 15 5 [出力例] 50 ※AtCoderテストケースより [入力例] 8 4 1 1 10 1 100 1 1000 1 [出力例] 36 ※AtCoderテストケースより [入力例] 15 3 10 1 5 3 7 4 [出力例] 179 [入力例] 12 5 6 7 1 5 7 1 7 3 11 9 [出力例] 97 [入力例] 35 10 3 3 13 17 20 2 5 16 12 15 7 11 10 23 5 19 17 22 2 15 [出力例] 682 [入力例] 2022 15 28 103 63 88 20 122 118 23 111 41 19 37 77 114 50 89 54 56 14 79 3 42 95 80 74 38 59 40 122 108 [出力例] 7603076 [入力例] 20220322 20 777 943 582 728 1000 522 703 623 117 1133 305 821 1177 1001 1324 621 680 575 527 243 951 665 543 426 574 509 720 1173 87 84 603 293 692 737 704 567 93 78 190 1092 [出力例] 3692618300173731 |
■参照サイト
AtCoder Regular Contest 021