C++の練習を兼ねて, AtCoder Beginner Contest 227 の 問題C (ABC conjecture) ～ 問題D (Project Planning) を解いてみた.
■感想.
1. 問題Dは, 二分探索の方針で検討したものの, 判定関数が見えなかったので, 解説を参考に, AC版に到達できた.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 227 解説 の 各リンク を ご覧下さい.
■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 |
// 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 main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. B を 固定したときの A, C の 個数. LL ans = 0; repx(b, 1, (int)sqrt(N) + 1){ repx(a, 1, b + 1){ LL c = N / (a * b); if(c >= b) ans += (c - b) + 1; else break; } } // 3. 出力. 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 |
[入力例] 4 [出力例] 5 ※AtCoderテストケースより [入力例] 100 [出力例] 323 ※AtCoderテストケースより [入力例] 100000000000 [出力例] 5745290566750 [入力例] 7 [出力例] 9 [入力例] 2021 [出力例] 13439 [入力例] 20211114 [出力例] 536312958 |
■C++版プログラム(問題D／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 |
// 解き直し. // https://atcoder.jp/contests/abc227/editorial/2911 // 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; LL K; scanf("%d %lld", &N, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 評価関数. auto f = [&](LL m) -> bool { // 2-1. m個以上のプロジェクトを作成できるか？ LL o = 0; rep(i, N) o += min(a[i], m); // 2-2. 判定結果. return (m <= o / K); }; // 3. 二分探索で確認してみる. // LL l = 0, h = 2e17 + 1, m; LL l = 0, h = 2e18 + 1, m; // テストケース(case_04.txt) で NG となったため, 修正. while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) l = m; else h = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4. 出力. printf("%lld\n", l); 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 |
[入力例] 3 3 2 3 4 [出力例] 2 ※AtCoderテストケースより [入力例] 4 2 1 1 3 4 [出力例] 4 ※AtCoderテストケースより [入力例] 4 3 1 1 3 4 [出力例] 2 ※AtCoderテストケースより [入力例] 5 3 2 5 12 16 25 [出力例] 17 [入力例] 5 3 2 5 12 18 19 [出力例] 18 [入力例] 5 3 2 5 12 25 26 [出力例] 19 [入力例] 30 5 51 40 69 20 57 53 85 103 59 45 54 36 106 36 108 54 23 74 54 115 51 98 28 111 14 60 105 51 106 60 [出力例] 385 [入力例] 60 7 143968 673147 442360 836832 419701 312333 409321 1052604 331047 1152522 1050980 374482 36309 862087 876431 904817 118489 796446 1075067 1170994 850846 564510 466887 368936 520578 128485 1061395 1169029 636245 797907 612395 861793 1156053 1219440 820464 953251 694532 670293 620020 845759 563298 230762 218198 784660 496413 377992 686019 1183415 1064335 386372 1031504 1034102 1108929 150314 530511 209176 571970 680992 514704 620123 [出力例] 5786077 [入力例] 100 11 1024501679 432300252 711933293 751510314 817097636 571084915 913664931 290328615 202462701 497433395 551433422 794760635 1032819249 158046377 685486175 364539343 797691083 786118670 768254660 271146884 1090909860 530625902 1194134546 233219966 1167927310 466581498 11363299141 941737868 22896929 2442499370 4822707 630671761 198619739 247153309 567133826 201648231 201283771 17250183 653527938 1196698698 540477135 681998865 10802691547 607194413 705916648 711159161 557757099 465991201 726423073 1152413183 661237656 967111521 1177078300 491129186 1126170273 288057207 478189316 746709355 244663800 431617238 839108540 926642182 301630237 791946161 1051559761 1230751212 596770253 242151194 333912399 1110331404 480986811 911846005 730919848 1171935205 368032628 968229990 1189200274 965768086 472393882 260047484 1045594673 905464959 862626471 8810402505 831520978 610164180 227037971 771013523 118804047 894125994 4550884525 599408963 818696628 1124244223 1174937406 152595882 271334769 716664895 807452882 3370179580 [出力例] 8977841209 |
■参照サイト
キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)