C++の練習を兼ねて, AtCoder Regular Contest 118 の 問題A (Tax Included Price) ～ 問題B (Village of M People) を解いてみた.
■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 問題Bは, 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 118 解説 の 各リンク を ご覧下さい.
■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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// 解き直し. // https://atcoder.jp/contests/arc118/editorial/1200 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 t, N; scanf("%d %d", &t, &N); --N; // 2. 税込み価格として現れないものは？ LL bef = 0, cur = 0; vl v; rep(a, 100){ // 今回分計算. cur = (LL)((100 + t) * (a + 1) / 100); // 差分が, 1 より大きいものは？ if(cur - bef > 1) v.pb(cur - 1); // 前回分保存. bef = cur; } // for(auto &p : v) printf("%lld\n", p); // 3. 周期性. int f = (LL)v.size(); LL q = N / f; int r = N % f; // 4. N番目の金額は？ LL ans = q * (LL)(100 + t) + v[r]; // 5. 出力. 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 |
[入力例] 10 1 [出力例] 10 ※AtCoderのテストケースより [入力例] 3 5 [出力例] 171 ※AtCoderのテストケースより [入力例] 1 1000000000 [出力例] 100999999999 ※AtCoderのテストケースより [入力例] 22 20210509 [出力例] 112076458 [入力例] 35 20220428 [出力例] 77993079 |
■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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
// 解き直し. // https://atcoder.jp/contests/arc118/editorial/1226 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 K; LL N, M; scanf("%d %lld %lld", &K, &N, &M); rep(i, K) scanf("%lld", &a[i]); // 2. 評価関数. auto f = [&](LL m) -> bool { // 2-1. B[i] の 設定(※ L[i] を ベース). LL t = 0; vl b(K); rep(i, K){ LL p = (max(0LL, M * a[i] - m) + (N - 1)) / N; b[i] = p; t += p; } // 2-2. B[i] の 設定(※ R[i] を ベース). rep(i, K){ LL q = (M * a[i] + m) / N; LL d = max(0LL, min(q - b[i], M - t)); if(d){ b[i] += d; t += d; } } // 2-3. 判定結果(t < M だと, 02_rand_01.txtなどで, WAとなるように見える). return (t == M); }; // 3. 二分探索で確認してみる(※01_sample_02.txt などのWA回避のため, l = 0 を l = 1 に 修正). LL l = 1, h = 2e16 + 1; while(l + 1 < h){ LL m = (h + l) >> 1LL; if(f(m)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4. 復元. // 4-1. B[i] の 設定(※ L[i] を ベース). LL t = 0; vl ans(K); rep(i, K){ LL p = (max(0LL, M * a[i] - h) + (N - 1)) / N; ans[i] = p; t += p; } // 4-2. B[i] の 設定(※ R[i] を ベース). rep(i, K){ LL q = (M * a[i] + h) / N; LL d = max(0LL, min(q - ans[i], M - t)); if(d){ ans[i] += d; t += d; } } assert(t == M); // 5. 出力. rep(i, K) printf("%lld%s", ans[i], (i < K - 1) ? " " : "\n"); 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 7 20 1 2 4 [出力例] 3 6 11 ※AtCoderテストケースより [入力例] 3 3 100 1 1 1 [出力例] 34 33 33 ※AtCoderテストケースより [入力例] 6 10006 10 10000 3 2 1 0 0 [出力例] 10 0 0 0 0 0 ※AtCoderテストケースより [入力例] 7 78314 1000 53515 10620 7271 3817 1910 956 225 [出力例] 683 136 93 49 24 12 3 ※AtCoderテストケースより [入力例] 5 55 111 5 7 9 11 23 [出力例] 10 14 18 22 47 [入力例] 24 2022 20210509 314 159 265 358 97 9 323 84 62 64 33 83 27 9 50 28 8 4 19 7 1 6 9 3 [出力例] 3138526 1589254 2648756 3578320 969545 89958 3228484 839606 619709 639700 329845 829610 269873 89958 499765 279868 79962 39981 189911 69967 9995 59972 89958 29986 [入力例] 50 33333 20220429 780 375 1010 1215 759 999 1038 370 381 366 40 321 1149 896 987 794 734 1143 452 579 284 276 204 635 264 47 37 768 1234 332 572 1002 320 1169 201 738 526 453 895 1090 798 774 411 1143 1086 685 194 931 1035 841 [出力例] 473163 227482 612685 737042 460424 606012 629670 224449 231122 222023 24265 194725 697005 543531 598733 481655 445258 693365 274192 351232 172280 167427 123750 385203 160147 28511 22445 465883 748568 201398 346986 607832 194118 709138 121930 447685 319082 274798 542924 661215 484082 469523 249320 693365 658788 415534 117684 564762 627851 510167 [入力例] 100 777777 1000000000 5526 6946 12205 9758 7777 11193 5678 2804 12305 6582 7081 10594 6520 12118 13896 12845 9471 5550 3456 550 3305 3349 3310 2056 12466 10186 15169 10686 8320 9999 3829 12188 7777 4003 6666 15007 824 11590 4772 7330 3839 2093 1535 7847 2997 3699 14379 5615 14035 10732 1991 439 8622 5877 14232 10831 10438 10039 7959 1907 8696 9839 10527 12638 9289 3129 4332 2765 2345 7397 12379 10160 12263 10541 9308 13260 13176 7980 5000 1285 3559 7560 956 7814 10833 5501 13091 10596 11873 15246 7777 1796 4315 12627 11846 2597 15154 3257 6950 3327 [出力例] 7104864 8930580 15692159 12546013 9999010 14391014 7300293 3605146 15820730 8462580 9104152 13620871 8382866 15580301 17866304 16515016 12177012 7135721 4443433 707144 4249290 4305861 4255719 2643431 16027730 13096299 19503019 13739157 10697154 12855870 4923005 15670301 9999010 5146719 8570580 19294734 1059430 14901443 6135435 9424295 4935862 2691003 1973573 10089010 3853290 4755862 18487304 7219293 18045018 13798299 2559860 564429 11085440 7556150 18298304 13925585 13420299 12907299 10233010 2451860 11180583 12650155 13534728 16248873 11943012 4023004 5569720 3555004 3015003 9510438 15915873 13062870 15766730 13552728 11967441 17048588 16940588 10260010 6428578 1652144 4575862 9720010 1229144 10046581 13928157 7072721 16831303 13623442 15265301 19602020 9999010 2309145 5547863 16234731 15230587 3339003 19483734 4187576 8935723 4277576 |
■参照サイト
AtCoder Regular Contest 118