C++の練習を兼ねて, AtCoder Regular Contest 144 の 問題A (Digit Sum of 2x) ～ 問題B (Gift Tax) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 問題B で, 二分探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 141 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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; #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--) #define pb push_back int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. M. int M = 2 * N; // 3. x. int q = N / 4; int r = N % 4; string x; if(r) x.pb(r + '0'); rep(i, q) x.pb('4'); // 4. 出力. printf("%d\n%s\n", M, x.c_str()); 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 ※AtCoderのテストケースより [入力例] 6 [出力例] 12 24 ※AtCoderのテストケースより [入力例] 100 [出力例] 200 4444444444444444444444444 ※AtCoderのテストケースより [入力例] 7 [出力例] 14 34 [入力例] 21 [出力例] 42 144444 [入力例] 55 [出力例] 110 34444444444444 [入力例] 2022 [出力例] 4044 24444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 |
■C++版プログラム(問題B／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 |
// 解き直し. // https://atcoder.jp/contests/arc144/editorial/4438 // 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[303030]; int main(){ // 1. 入力情報. int N, a, b; scanf("%d %d %d", &N, &a, &b); LL aMax = 0; rep(i, N){ scanf("%lld", &A[i]); aMax = max(aMax, A[i]); } // 2. 評価関数. auto f = [&](LL C) -> bool { // 2-1. 任意 の i で, A[i] >= C を 達成できるか？ LL x = 0, y = 0; rep(i, N){ // 差分. LL d = abs(C - A[i]); // +a 操作. if(A[i] < C){ x += d / a; x += (d % a) > 0; } // -b 操作. if(A[i] >= C) y += d / b; } // 2-2. 判定結果. return (x <= y); }; // 3. 二分探索で確認してみる. LL l = -1, h = aMax * 2 + 1; 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 |
[入力例] 3 2 2 1 5 9 [出力例] 5 ※AtCoderのテストケースより [入力例] 3 2 3 11 1 2 [出力例] 3 ※AtCoderのテストケースより [入力例] 3 1 100 8 5 6 [出力例] 5 ※AtCoderのテストケースより [入力例] 6 123 321 10 100 1000 10000 100000 1000000 [出力例] 90688 ※AtCoderのテストケースより [入力例] 10 20 22 314 159 265 358 979 323 846 264 338 327 [出力例] 399 [入力例] 12 2022 2023 48777 62245 64053 48929 50177 34066 62213 19468 65086 76308 36458 60626 [出力例] 51820 [入力例] 33 123456789 234567890 119462232 441702612 741000538 75937058 249169418 88678388 322309006 934544728 382109572 200174813 579938761 629008023 922337708 321026352 72252172 312780367 202788116 381989156 254895422 726096598 313540074 392866546 879268330 653653149 384616870 261814030 36273445 535329540 106843016 868666234 758681421 156962817 133682619 [出力例] 256960818 [入力例] 50 11 15 2244 9171 5910 9145 7923 1959 4653 7101 7913 9403 9144 3185 5328 9177 2117 134 6376 6425 8190 9558 7087 9909 4856 4663 9774 9330 3626 8179 3955 5244 1060 9881 6784 7292 543 6069 7909 2869 232 7170 2628 4975 622 2394 1279 4281 6452 2930 8750 264 [出力例] 5102 |
■参照サイト
AtCoder Regular Contest 144