C++の練習を兼ねて, AtCoder Regular Contest 146 の 問題A (Three Cards) ~ 問題B (Plus and AND) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 個人的には, 問題B で, 二分探索(応用版, 集合を考慮) の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 146 解説 の 各リンク を ご覧下さい.
■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 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using vvl = vector<vl>; #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; scanf("%d", &N); vvl v(6); rep(i, N){ int a; scanf("%d", &a); if(a < 10) v[0].pb(a); else if(a < 100) v[1].pb(a); else if(a < 1000) v[2].pb(a); else if(a < 10000) v[3].pb(a); else if(a < 100000) v[4].pb(a); else v[5].pb(a); } // 2. sort. rep(i, 6){ sort(all(v[i])); reverse(all(v[i])); } // 3. 整数を, 最大 18個 選ぶ. vl t; rep(i, 6) rep(j, min(3, (int)v[i].size())) t.pb(v[i][j]); // 4. 整数(3個)から作成した整数の最大値は? LL ans = 0; int n = t.size(); rep(i, n){ rep(j, n){ rep(k, n){ if(i != j && j != k && k != i){ string s = to_string(t[i]); s += to_string(t[j]); s += to_string(t[k]); ans = max(ans, stoll(s)); } } } } // 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 |
[入力例] 5 1 4 3 5 8 [出力例] 854 ※AtCoderのテストケースより [入力例] 8 813 921 481 282 120 900 555 409 [出力例] 921900813 ※AtCoderのテストケースより [入力例] 10 11 8 9 5 6 7 8 777 2 3 [出力例] 977711 [入力例] 20 12345 487 8080 123 7070 220 3763 1665 5164 1638 4271 1302 3184 241 630 12 1861 3565 987 999 [出力例] 8080707012345 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc146/editorial/4634 // 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() LL a[202020]; int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 評価関数. auto f = [&](LL X) -> bool { // 2-1. X の 上位集合に含まれる最小の整数 b[i]. vl v; rep(i, N){ LL b = X; repr(j, 31, 0){ // X の jbit目 が 1. LL bit = 1LL << j; if(b & bit) continue; // X の jbit目 が 0. LL t = b | (bit - 1); if(t < a[i]) b |= bit; } // 差分. v.pb(b - a[i]); } // 2-2. sort. sort(all(v)); // 2-3. (K要素)操作回数. LL d = 0; rep(i, K) d += v[i]; // 2-5. 判定結果. return (d > (LL)M); }; // 3. 二分探索で確認してみる. LL l = 0, h = (1LL << 32) + 1LL; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) h = m; else 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 |
[入力例] 4 8 2 1 2 4 8 [出力例] 10 ※AtCoderテストケースより [入力例] 5 345 3 111 192 421 390 229 [出力例] 461 ※AtCoderテストケースより [入力例] 7 18 5 3 4 8 11 12 17 23 [出力例] 16 [入力例] 10 50 7 80 100 92 34 115 59 103 107 112 101 [出力例] 106 [入力例] 50 20220823 17 106255686 84374702 102511172 86199041 20471611 20311296 25895741 120233844 66769765 116404889 86089818 109694206 50780701 58043255 91938819 51432612 80712996 95142878 41522855 34035448 59244373 58566447 45185189 47990981 116692991 68140874 82529468 98511521 50416527 75089014 57540828 37157784 75212891 64977902 31486499 10838381 13836513 35242992 48366115 12313711 35495113 92933260 52126220 32483328 99177008 55365265 108962428 69874519 16053102 55722329 [出力例] 72576026 [入力例] 500 123456789 111 680 832 391 2592 749 3698 5432 649 2973 2499 4400 3107 378 1875 2858 3135 3233 3088 1539 4483 292 2256 43 3530 4733 1043 2671 2946 2906 831 5167 4084 3297 2991 2092 5247 3232 566 2818 4460 3748 1728 2182 3735 175 49 384 330 3731 5155 2727 2740 4824 2638 4893 2006 759 3428 4417 28 837 712 698 52 1032 4380 778 2632 1284 4571 119 5415 2338 671 4897 3129 3819 988 171 5457 3724 1806 2536 212 4444 3564 5124 2434 3372 699 1557 2015 1893 1329 2473 2123 1051 211 3316 4260 4507 2841 2131 1701 2042 2903 1865 3026 2537 2366 4223 4718 2520 5479 3421 2271 2797 5087 2515 1364 1208 3269 1571 2583 2378 1379 2196 5247 3440 3115 3986 2084 3964 2054 3843 639 4010 4303 4769 4615 2755 4114 2330 2901 1816 5554 875 5121 654 3069 2624 1121 3296 1622 3882 2166 3230 3666 4968 4488 900 103 998 4527 5020 3320 5087 5284 880 4634 3351 2915 3460 2519 506 1383 1037 1074 108 5279 1575 4675 2074 1704 731 3293 2269 5169 5253 3887 4754 3919 5225 1019 3616 4083 393 4651 31 1364 3206 2343 5474 4904 4538 3121 3732 5200 700 57 4168 533 2286 615 4986 4238 1983 956 3266 5314 3133 1060 2150 1783 780 1206 1122 4424 2431 3900 2456 621 1449 1293 4326 3316 1267 2879 2375 3294 5064 3148 844 2211 5042 2959 1514 480 3418 2831 3601 948 4114 4042 3076 4022 159 3060 1570 697 3182 1746 4473 3548 1599 4910 300 14 1537 3014 95 4629 4240 1027 4785 3510 1461 4875 2042 4740 3801 3127 1581 4747 3386 2181 2985 1322 1378 4341 4516 218 442 3795 2946 1967 1536 513 1415 475 5509 2023 968 162 2344 1061 710 2823 4978 3573 2838 1485 2429 2169 5549 2598 3511 3115 319 874 3594 2284 991 3339 5186 2285 3321 2021 2933 3121 3143 2873 4050 1613 2136 3085 2051 3736 5195 2081 4454 1644 1837 616 2332 1141 374 597 2865 4596 1971 2263 2823 1430 4658 3672 1565 1845 908 3970 1871 5115 1718 497 4440 88 4024 5136 3260 2716 4313 1285 4984 1385 4443 5164 1958 4575 2518 5431 1445 1536 4560 495 636 5002 302 3208 4775 2729 535 4576 121 662 97 696 4157 1167 4022 4796 4541 4236 2431 2102 2901 2763 5474 5211 1508 4290 1667 4460 4659 3899 3880 2462 2895 577 4882 1859 3844 2211 837 1696 4273 5210 4562 1716 29 2078 105 1349 3943 4370 1787 4968 260 1423 1197 2524 1027 5343 5226 132 1731 4900 4942 3422 4667 1625 3437 2107 5438 2513 904 486 2420 4224 1537 3514 1541 925 2920 736 5406 1952 3007 3333 290 4163 3085 2850 4015 4045 5209 5050 1652 340 2459 3461 1745 909 4630 868 3815 4233 2138 5494 3326 4160 1784 2108 3693 447 976 2192 1535 1657 184 5388 [出力例] 1117090 |
■参照サイト
AtCoder Regular Contest 146