C++の練習を兼ねて, AtCoder Beginner Contest 155 の 問題D (Pairs) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 155 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/abc155/editorial.pdf // 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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; LL K, a; vl vm, vp, vz; scanf("%d %lld", &N, &K); rep(i, N){ scanf("%lld", &a); if(a < 0) vm.pb(-a); if(a > 0) vp.pb(a); if(a == 0) vz.pb(0); } // 2. 負, 零, 正 の ペア. // 負: 1 ~ mCount // 零: mCount + 1 ~ zCount // 正: zCount + 1 ~ (LL)N * (LL)(N - 1) / 2 LL nm = vm.size(); LL np = vp.size(); LL nz = vz.size(); LL mCount = nm * np; LL zCount = mCount + nz * (nz - 1) / 2 + nz * (LL)(N - nz); // 3. sort. sort(all(vm)); sort(all(vp)); // 4. K 番目 が 負. if(K <= mCount){ // 4-1. 評価関数. auto f = [&](LL X) -> bool { // ペアで, X以上となる個数. LL ret = 0; rep(i, nm){ LL q = X / vm[i]; int at = lower_bound(all(vp), q) - vp.begin(); while(at < np && vm[i] * vp[at] < X) ++at; ret += np - at; } // 判定結果. return (ret >= K); }; // 4-2. 二分探索で確認してみる. LL l = 0, h = 2e18 + 1, m; while(l + 1 < h){ LL m = (h + l) >> 1LL; if(f(m)) l = m; else h = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4-3. 出力. printf("%lld\n", -l); } // 5. K 番目 が 零. if(K > mCount && K <= zCount) puts("0"); // 6. K 番目 が 正. if(K > zCount){ // 6-1. 評価関数. auto f = [&](LL X) -> bool { // ペアで, X以上となる個数(負). LL ret = 0; rep(i, nm){ LL q = X / vm[i]; int at = lower_bound(all(vm), q) - vm.begin(); while(at < nm && vm[i] * vm[at] < X) ++at; ret += nm - max(at, i + 1); } // ペアで, X以上となる個数(正). rep(i, np){ LL q = X / vp[i]; int at = lower_bound(all(vp), q) - vp.begin(); while(at < np && vp[i] * vp[at] < X) ++at; ret += np - max(at, i + 1); } // 判定結果. return (ret >= (LL)N * (LL)(N - 1) / 2 - K + 1); }; // 6-2. 二分探索で確認してみる. LL l = 0, h = 2e18 + 1, m; while(l + 1 < h){ LL m = (h + l) >> 1LL; if(f(m)) l = m; else h = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 6-3. 出力. 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 |
[入力例] 4 3 3 3 -4 -2 [出力例] -6 ※AtCoderテストケースより [入力例] 10 40 5 4 3 2 -1 0 0 0 0 0 [出力例] 6 ※AtCoderテストケースより [入力例] 30 413 -170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0 [出力例] 448283280358331064 ※AtCoderテストケースより [入力例] 32 100 6 -4 1 11 9 6 7 -6 4 3 11 4 9 -4 5 0 -6 -5 11 0 -8 6 -5 8 11 -10 6 5 4 10 -9 6 [出力例] -36 [入力例] 100 2022 61 54 58 86 116 5 22 99 57 96 66 23 -66 -8 84 -112 99 15 15 61 18 39 19 -4 30 79 3 54 -84 101 68 55 42 48 70 85 14 1 60 2 38 25 0 66 110 8 122 95 105 54 47 8 57 0 113 0 69 72 11 28 77 10 4 92 15 100 111 75 -114 69 -55 68 115 -98 103 -88 96 62 76 39 15 23 13 107 67 101 100 104 59 122 -22 116 18 87 119 121 96 48 46 37 [出力例] 810 [入力例] 500 123456 9335 3944 3417 4250 11000 5835 -10891 5495 2109 4495 1512 976 11827 8877 8514 7942 8991 642 2459 1567 -11710 5827 10069 7089 5160 2361 1851 11615 7462 2511 6510 9731 -2596 -9952 10391 6923 11173 8934 3891 4978 11855 4164 -10466 3346 7092 3505 3669 123 7658 -11383 5487 9148 8546 9899 -1748 11251 11662 6712 11364 4217 8934 5624 3530 10779 5004 10737 3559 12145 3905 11180 307 10907 1420 648 6141 8981 -10137 705 8542 -10782 851 46 3111 5739 9808 910 7272 3690 4042 11167 572 11661 10423 3593 6812 7501 -12021 10112 -11188 -7773 4252 7439 1518 5973 6619 2976 3564 6070 2273 6745 5361 9472 932 4624 3861 1975 4616 8289 6416 5693 10601 9241 6184 2230 5242 7116 11063 -9305 8582 6848 6082 11589 10273 3721 -11313 6430 5217 1278 4734 11468 9379 5170 6300 -573 10122 3157 -4433 6667 7636 5556 -5632 7591 10277 9515 875 2057 2171 -12043 11848 100 7520 8304 8985 9323 1401 3588 9434 6842 9175 2262 4764 4976 9345 10830 8318 7875 9732 12322 8453 4908 3128 3915 8852 8211 8038 10484 476 6113 4469 1125 7068 -1025 3946 9268 9781 6543 2111 9918 -7381 753 998 12065 6851 10543 -4516 9740 1996 1267 3318 1168 1698 756 7591 1193 -10789 4680 -10749 2717 8364 1709 7056 313 -12043 7427 1922 10593 2707 8311 6788 2813 3342 6921 11480 7225 7425 4613 7238 6576 2287 6908 -6357 10794 11999 4226 8213 1878 -1892 1177 10463 8186 -11557 11051 1662 9945 8059 9921 3462 9390 8277 5947 4396 2081 9825 -4092 11293 11834 9337 909 8200 6236 11053 11505 11909 9464 7190 654 889 3779 12183 8962 11940 8112 8421 9701 4286 5259 4151 -1655 8782 5989 6652 2605 3278 7442 9091 4828 10335 4303 692 3046 10991 4897 1120 5681 3194 7806 -7807 1434 11209 147 9057 -5880 4630 4956 3426 12087 -3982 -11836 7248 574 7828 10259 1989 3601 1159 11069 8723 9463 -10726 480 1994 3501 6181 3574 7705 -9485 3239 365 5479 11394 6226 3992 3518 -10092 3467 3344 7689 4032 6358 7667 8296 4997 5351 4806 7274 6360 8812 -2507 -4692 -5065 2396 12112 6426 1621 7241 3169 -4416 10127 784 1122 9859 -10271 9159 10223 6047 12146 4507 4766 2018 2046 7446 1055 3004 8453 6973 775 8296 1997 3348 7894 505 4162 1984 4140 10912 -10471 7963 4503 2614 10364 8667 2130 5784 3578 3130 8981 -12323 2411 8183 8241 -8861 1923 2680 8126 3885 -9200 -6852 -10541 7872 1231 -8718 451 478 3441 -10802 10017 4217 7088 9451 -9700 10607 4292 8920 -10601 9517 -5043 1101 -13108 8274 7536 8908 8500 5864 -10837 8651 1642 6122 -11759 11413 11317 2536 -4625 -4658 7541 528 -10230 -7926 9626 10548 10155 7766 2005 -7346 10132 8516 -10853 551 7515 5526 10232 10205 1002 10570 -8776 -11922 5902 7924 3858 2967 -1777 7246 1502 785 10691 12053 94 7334 7377 -10656 40 2597 3327 4805 3781 9262 -10589 7053 12320 6780 -7329 [出力例] 123934756 |
■参照サイト
AtCoder Beginner Contest 155