C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題F (Dist Max 2) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 問題F で, 二分探索 および 尺取り法 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 215 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc215/editorial/2492 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; #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 a first #define b second #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp v(N); rep(i, N) scanf("%lld %lld", &v[i].a, &v[i].b); // 2. sort. sort(all(v)); // 3. 評価関数. // -> 距離 K 以上 の ペアがあるか？ auto f = [&](LL K) -> bool { int l = 0; LL yMin = 1e9 + 1, yMax = -1; rep(r, N){ int cur = l; // 各座標情報(右側). LL sx = v[r].a; LL sy = v[r].b; repx(j, cur, r + 1){ // 各座標情報(左側). LL gx = v[j].a; LL gy = v[j].b; // 終了. if(sx - gx < K) break; // 最小値, 最大値更新. yMin = min(yMin, gy); yMax = max(yMax, gy); // 見つかった場合. if(yMin <= sy - K || yMax >= sy + K) return true; // 次へ. l = j; } } // 見つからなかった場合. return false; }; // 4. 二分探索で確認してみる. LL l = -1, h = 2e9 + 1, m; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) l = m; else h = m; } // 5. 出力. 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 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 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 |
[入力例] 3 0 3 3 1 4 10 [出力例] 4 ※AtCoderテストケースより [入力例] 4 0 1 0 4 0 10 0 6 [出力例] 0 ※AtCoderテストケースより [入力例] 8 897 729 802 969 765 184 992 887 1 104 521 641 220 909 380 378 [出力例] 801 ※AtCoderテストケースより [入力例] 20 94 47 81 102 1 9 45 82 49 5 4 0 110 100 104 66 44 35 30 104 50 90 9 19 34 109 2 116 121 60 89 83 94 20 37 113 63 94 89 55 [出力例] 100 [入力例] 50 85 448 943 216 761 879 224 293 768 664 617 775 106 1166 252 798 921 811 611 746 545 289 162 1177 30 1117 530 913 766 858 988 297 404 207 80 149 878 1056 162 490 0 927 402 1069 871 322 380 1041 345 1131 1189 446 607 1135 643 1066 694 344 474 1162 50 514 1054 1106 37 1056 1090 1218 474 76 912 906 865 166 853 200 283 870 414 343 183 180 1099 733 1056 230 692 1074 1011 914 691 1143 728 251 964 1017 588 1142 239 1062 [出力例] 1010 [入力例] 100 286033 1217893 664787 230009 947285 1162937 750486 116732 79391 988295 639738 364720 868752 369477 254524 222021 966435 870148 778311 1166200 388526 988972 894196 31825 436771 261880 1077274 249524 716297 1152108 746185 556348 93283 1087575 1111088 438298 596568 22609 524686 855060 382247 861072 36078 388585 194112 429271 782995 138807 1172838 632330 591733 692833 978763 405768 620759 802057 1010149 942025 1180449 978699 972169 731259 101210 998916 970443 574502 389234 498472 43488 393092 1141701 928848 974239 332735 307946 735292 700332 530765 105892 902668 1096578 189964 972122 16451 802819 1078840 757005 953590 69424 137776 1148394 457930 646654 681723 576772 531513 411683 1062036 1177876 1039889 1116350 876345 811266 930392 485282 498721 435481 29193 281045 863100 141626 231940 145172 1037358 612239 1040466 605107 735442 688082 1183399 1103928 333561 27995 1048724 346709 656492 652222 979437 507995 437219 903619 21833 913903 1053229 850703 485558 312095 313053 464226 852029 396691 634270 1003024 1030050 104968 1025267 242293 960715 484993 828327 250189 29449 960538 50219 385467 965721 479300 462724 483741 785154 1098644 1137776 155363 867808 1172060 97921 560779 858203 1091400 1127842 86940 1084870 1124662 196631 864314 752303 1218237 739770 355224 582086 185230 1153750 196179 352570 916618 13590 851336 1147358 562513 230921 562686 499132 705064 621079 313336 526612 306605 772850 258570 797791 [出力例] 1000000 |
■参照サイト
AtCoder Beginner Contest 215