C++の練習を兼ねて, AtCoder Beginner Contest 174 の 問題E (Logs) を解いてみた.
■感想.
1. 二分探索の方針で, 何とか, AC版まで持って行けたので, 良かったと思う.
2. 二分探索自体の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 174 解説をご覧下さい.
■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 |
// 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[202020]; int main(){ // 1. 入力情報. int N; // handmade13, handmade14 で, WAのため, ロジック修正(l = 1 でなく, l = 0 に修正). LL K, l = 0, h = 0, m; scanf("%d %lld", &N, &K); rep(i, N){ scanf("%lld", &a[i]); h = max(h, a[i]); } // 2. 丸太の分割. auto f = [](LL aMax, LL k, int n) -> bool { // ex. // 18 を 2回分割すると, 長さ 6 の 丸太 が 3つ. // -> 18 ÷ (長さ 6) = 3 だが, 分割回数は, 2回 なので 注意. LL ok = 0; rep(i, n){ ok += a[i] / aMax; if(a[i] % aMax == 0) ok--; } return (ok <= k); }; // 二分探索で確認してみる. while(l + 1 < h){ m = (h + l) >> 1; if(f(m, K, N)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 3. 出力. printf("%lld\n", h); 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 |
[入力例] 2 3 7 9 [出力例] 4 ※AtCoderテストケースより [入力例] 3 0 3 4 5 [出力例] 5 ※AtCoderテストケースより [入力例] 10 10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202 [出力例] 292638192 ※AtCoderテストケースより [入力例] 15 13 7467 8273 5122 9914 706 3161 10102 10235 550 1882 2257 2683 2773 6850 7325 7896 [出力例] 3663 [入力例] 32 25 924384 687084 454364 689235 161747 1099367 212905 694836 1116187 968366 464715 786971 1202407 511094 584242 127861 617279 782931 822489 1142664 921876 342648 792532 523389 206848 903297 402983 299458 637298 22901 769063 354711 [出力例] 484183 |
■参照サイト
AtCoder Beginner Contest 174