C++の練習を兼ねて, AtCoder Grand Contest 034 の 問題C (Tests) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
※ 但し, 解説の内容を把握するまでに時間がかかり, 評価関数の実装に, 非常に苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 034 解説 を ご覧下さい.
■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 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 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/agc034/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<LL, LL, 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 all(x) x.begin(), x.end() LL tCum[101010]; int main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); vector<T3> v; rep(i, N){ LL b, l, u; scanf("%lld %lld %lld", &b, &l, &u); v.emplace_back(b, l, u); } // 2. 初期値 ΣDi[0]. LL base = 0; rep(i, N){ LL b = get<0>(v[i]); LL l = get<1>(v[i]); base -= b * l; } // 3. sort. // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/ // 長さ X(l[i] … b[i]個, u[i] … (X - b[i])個) の 数列 // {l[i], l[i], ..., l[i], u[i], u[i], ..., u[i]} を 要素の和の大きい順に並び替える. sort(all(v), [&](const T3 &x, const T3 &y){ LL bx = get<0>(x), by = get<0>(y); LL lx = get<1>(x), ly = get<1>(y); LL ux = get<2>(x), uy = get<2>(y); LL rx = lx * bx + ux * (X - bx); LL ry = ly * by + uy * (X - by); return rx > ry; }); // for(auto &p : v) printf("b=%lld l=%lld u=%lld\n", get<0>(p), get<1>(p), get<2>(p)); // 4. 累積和. rep(i, N){ LL b = get<0>(v[i]), l = get<1>(v[i]), u = get<2>(v[i]); tCum[i + 1] = tCum[i] + (l * b + u * (X - b)); } // 5. 評価関数. // -> 二分探索を使うので, 評価関数内では, (入力情報 v の)sortは, 行わないこと(単調性が失われるため). auto f = [&](LL k) -> bool { // 5-1. 数列から, k個選択する場合に必要な情報を取得. int q = (int)(k / X); LL r = k % X; // 5-2. 余りがゼロの場合. LL D = base + tCum[q]; // 5-3. 余りがゼロでない場合. if(r){ // r個選択する数列を, N個の数列から, 1個選択していく. // index は, [0, q - 1]. rep(i, q){ LL b = get<0>(v[i]), l = get<1>(v[i]), u = get<2>(v[i]); D = max(D, base + tCum[q + 1] - (tCum[i + 1] - tCum[i]) + (l * min(b, r) + u * max(0LL, r - b))); } // index は, [q, N - 1]. repx(i, q, N){ LL b = get<0>(v[i]), l = get<1>(v[i]), u = get<2>(v[i]); D = max(D, base + tCum[q] + (l * min(b, r) + u * max(0LL, r - b))); } } // 5-4. 判定結果. return (D >= 0); }; // 6. 二分探索. // -> 最小値: -1, 最大値: X * N + 1 として実施. LL l = -1LL, h = X * (LL)N + 1LL, m; while(l + 1 < h){ m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 7. 出力. 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 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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
[入力例] 2 100 85 2 3 60 1 1 [出力例] 115 ※AtCoderのテストケースより [入力例] 2 100 85 2 3 60 10 10 [出力例] 77 ※AtCoderのテストケースより [入力例] 1 100000 31415 2718 2818 [出力例] 31415 ※AtCoderのテストケースより [入力例] 10 1000 451 4593 6263 324 310 6991 378 1431 7068 71 1757 9218 204 3676 4328 840 6221 9080 684 1545 8511 709 5467 8674 862 6504 9835 283 4965 9980 [出力例] 2540 ※AtCoderのテストケースより [入力例] 5 10 0 3 5 2 1 6 5 2 8 5 4 6 4 5 5 [出力例] 11 [入力例] 12 12 8 7 11 2 7 8 1 8 8 10 8 16 8 5 12 2 7 15 6 4 12 10 10 18 11 10 19 4 3 10 5 9 17 2 5 13 [出力例] 41 [入力例] 100 123 70 987 1425 19 416 743 24 35 317 8 765 1116 97 850 1490 93 250 343 35 838 1748 89 530 1403 93 945 1547 40 796 1522 79 599 1070 110 465 1148 63 899 1679 121 141 258 121 991 1131 1 300 1074 93 210 671 1 954 1120 117 989 1462 101 725 1709 112 793 1106 54 758 1132 88 756 1721 7 331 798 50 123 1024 104 779 1603 74 348 497 77 500 1066 71 475 1320 28 86 734 3 699 1034 109 532 1096 87 255 419 118 873 1573 89 683 755 35 778 1446 46 462 1011 91 730 1696 47 313 1042 94 883 884 0 592 850 60 148 415 20 146 250 34 569 1471 60 925 1192 94 412 497 98 676 1108 67 144 764 6 663 1264 43 449 737 121 890 1899 58 802 1687 29 920 1382 11 558 762 20 978 1163 13 609 1059 82 513 705 26 852 1544 91 100 251 63 54 746 72 445 774 44 314 569 47 195 656 41 112 394 86 319 1280 51 295 875 41 84 320 74 476 1313 34 762 1232 37 855 1125 58 661 1161 32 482 1104 12 864 1412 99 288 881 29 248 737 55 495 1110 83 100 121 5 435 942 107 369 1155 32 134 1136 21 794 1670 107 495 1433 120 622 1322 32 853 1748 101 851 1590 3 422 765 95 649 1323 36 944 1493 7 876 1426 104 167 641 32 544 1237 1 457 1047 53 419 1408 26 25 958 118 66 979 105 787 965 64 654 1367 30 655 951 93 560 1412 75 595 768 [出力例] 2605 |
■参照サイト
AtCoder Grand Contest 034