C++の練習を兼ねて, AtCoder Regular Contest 147 の 問題A (Max Mod Min) ~ 問題B (Swap to Sort) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題B で, 解説上の不一致度に着目するロジックが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 147 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi a(N); rep(i, N) scanf("%d", &a[i]); // 2. sort. sort(all(a)); // 3. 初期化. deque<int> dq; rep(i, N) dq.pub(a[i]); // 4. 操作. int ans = 0; while(dq.size() > 1){ int f = dq.front(); int b = dq.back(); int o = b % f; dq.pob(); if(o) dq.puf(o); ++ans; } // 5. 出力. printf("%d\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 33 34 35 36 |
[入力例] 3 2 3 6 [出力例] 3 ※AtCoderのテストケースより [入力例] 6 1232 452 23491 34099 57341 21488 [出力例] 12 ※AtCoderのテストケースより [入力例] 30 690839 681001 673615 114111 1173455 293172 906181 441519 317712 908733 1064265 878123 887479 667932 1051871 199356 431790 921027 926847 604481 1083959 314196 986396 198435 1079681 611949 102587 1037040 152797 571464 [出力例] 40 [入力例] 100 804525 118689 861132 422425 442375 257878 324931 704557 388539 1178755 437841 1177023 841380 148310 609048 14604 338624 131234 949468 1060690 178261 884195 907106 1135753 595559 866150 952572 390385 1019422 1180183 1025298 859197 1202522 795301 1102581 1176448 837332 295121 658009 866628 51756 505419 1065818 981407 122347 1114513 863223 176961 688853 1157438 714453 941949 133985 1103419 1182513 133395 924468 598392 782989 486935 216707 386947 580800 78067 663205 613537 1026505 71693 264315 504372 880813 1134919 1049543 338607 311239 412742 625586 994282 288497 404511 613004 1138285 610335 441416 1044753 130813 877580 992152 1122477 1061120 412998 303249 101010 1090380 1317832 982051 216534 699552 242477 978562 [出力例] 110 [入力例] 500 6779880 4971835 1015574 5352268 7070513 133441 8063840 10165894 10282398 11735140 7233410 11930946 11998886 3686385 8805484 4380571 7663517 11150208 7033995 2709335 1225454 495240 4525625 3173211 11271375 1205730 6677011 4829422 38186 2713695 10975492 5989794 2477361 6136054 4899823 1043044 7797391 6936257 11578227 6624862 8205359 8211221 6495623 4702766 9912380 8369740 5892730 3833142 10766361 790833 10508324 1142773 10129891 5235871 4996111 9477247 9115308 1213596 7227510 4493695 6985174 6095392 6600088 10302078 10514013 1826723 8748030 5103427 676617 5866650 10995329 8051169 2941351 4055602 508507 7419978 1170090 1463329 6470294 5808928 12194451 2344569 5411184 4452500 2469784 7947911 9934457 89185 9227252 6166318 4488795 11802055 8873635 6922597 4466650 5672410 10276288 3613278 2790632 9588031 896984 2325282 4605286 6048279 4344211 5664883 12289498 5634070 9966767 6543977 1962906 7624026 7824737 10853653 576718 5345231 2403229 4342226 10698482 10615315 2205578 3477321 1335700 3399911 1259451 8554750 8597987 7428304 4348887 4714576 4854819 7769133 926019 5596565 9161746 1526518 5645554 10575143 1739227 6307843 3304803 6789105 7886528 10858263 8734277 10164080 8895929 2337264 9209984 8549624 8608802 8628478 1641259 6266505 12174668 9686538 8208237 5255801 9777633 4137268 8020764 5463636 7641320 5574332 1611485 877627 2015614 265698 6181038 11487466 12002025 7226935 2049999 3066412 4745798 9651668 11441578 11510689 11392212 10313420 5362176 5467048 10606961 11559198 1026100 6486690 3585947 4289959 11177730 1563326 11875610 2539551 10524993 8074300 5629925 7356279 5986558 3021430 3042290 3023834 4073337 6109827 3447682 10663442 12329494 7408066 11066595 2215619 7886572 7702171 4912185 1212681 6357945 5305069 3772778 4668361 8925585 10530751 5739199 742173 70608848 7193524 7508657 347424 2851569 7147124 8076428 1699238 2412066 474361 9586071 1544585 900798 5011709 11568782 4624258 4047041 7866591 558011 12036468 4093305 3376693 4921964 1166065 1227564 10091356 4251395 4009801 9609174 1781296 2449601 433300 12020798 4561616 6444084 10989545 11433414 4491088 4175041 4101520 9751204 1411766 2931193 452652 8971040 703969 7261895 2365041 10019442 7824936 2738109 10743088 10131240 7116344 6908719 3351197 10652117 9979493 709422 5165045 3708986 10074236 3439944 9094454 4471097 3533551 1776052 12176435 11753268 8736835 11376227 12038239 1014104 628217 1665200 4692997 223742 1209022 2904028 1060070 4104362 8489825 9850826 8230595 3713250 5527162 902871 9863328 12302627 8801524 3095526 6883962 11140169 4531025 3216820 4258442 7730184 3535142 4980098 5981875 5373657 2784460 11292626 3146466 223716 8524830 3453136 4959252 11893591 497386 3129823 5409059 9572767 7034018 9201240 6335836 901817 12249987 2450342 10142141 4537381 9536295 8595477 9737932 3179766 8727207 9129442 9747369 2266677 7797706 3153061 7468753 4328422 6741557 7787271 2485820 128138 3585965 11974447 10743505 7256222 11481815 11987140 9060049 12119747 7401180 5741522 2942874 6493068 9206507 12093427 10933262 6954035 10965770 4646600 7540211 8439219 6153431 10112487 8600815 7981071 11364639 3714169 3056881 2571597 8366519 7063781 8051912 11388485 4937513 10945729 6827511 3326916 11193809 2570591 7634336 2637634 3087939 5606320 12051638 3842599 12221131 1808203 8544302 1228357 3476303 9164674 7737172 6022409 1585621 3651445 3872367 9623297 9849870 2850729 6427217 9780809 11513981 2007995 4843343 5833389 8351766 8925060 1136895 706898 1860852 5508373 11023490 2860900 9343123 4769002 3152618 2504216 1725735 8308050 3607069 1311706 11301077 3142780 9200852 9248901 7574290 6059147 5883443 83770 1390120 9810233 8822867 1106626 10217929 4454732 6625713 3891056 4526185 121713503 2373259 9348404 10152689 3132226 4085007 3900658 9434021 1737495 2210026 7536394 7374497 11324217 12285723 8123861 4541797 6245306 8295958 424095 4799787 12020867 9874591 9705068 9102631 12089867 310680 4324117 7702818 8007148 11756467 3357439 2202436 1605567 7013801 3174623 7487433 1541473 9029428 9079914 1039420 487580 1566390 3683100 7634560 10486548 3797205 [出力例] 515 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc147/editorial/4668 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; using vi = vector<int>; #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); vi p(N + 1); rep(i, N) scanf("%d", &p[i + 1]); // 2. sort. // 2-1. 操作 B(悪いインデックスを端に集める). vp ans; vi d(N + 1); repx(i, 1, N + 1) if((i + p[i]) % 2 != 0) d[i] = 1; bool ok = false; while(!ok){ ok = true; repr(i, N, 2){ if(i > 2 && !d[i - 2] && d[i]){ ok = false; ans.pb({1, i - 2}); swap(p[i - 2], p[i]); swap(d[i - 2], d[i]); } } } // 2-2. 操作 A(不一致度を 0 にする). repex(i, 1, N + 1, 2){ if(d[i]){ ans.pb({0, i}); swap(p[i], p[i + 1]); } } // 2-3. 操作 B(p[i] > p[i + 2] を 入れ替え). ok = false; while(!ok){ ok = true; repx(i, 1, N - 1){ if(p[i] > p[i + 2]){ ok = false; ans.pb({1, i}); swap(p[i], p[i + 2]); } } } vi z(N + 1); iota(all(z), 0); assert(z == p); // 3. 出力. printf("%d\n", ans.size()); for(auto &p : ans) printf("%s %d\n", p.a ? "B" : "A", p.b); 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 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 |
[入力例] 4 3 2 4 1 [出力例] 4 A 3 B 1 B 2 B 2 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 4 B 2 B 1 A 1 B 2 [入力例] 3 1 2 3 [出力例] 0 ※AtCoderテストケースより [入力例] 6 2 1 4 3 6 5 [出力例] 3 A 1 A 3 A 5 ※AtCoderテストケースより [入力例] 10 1 2 8 6 10 7 3 5 4 9 [出力例] 27 B 7 B 4 B 2 B 1 B 6 B 4 B 3 B 8 B 6 B 5 A 1 A 3 A 5 B 1 B 4 B 5 B 6 B 7 B 8 B 2 B 3 B 4 B 5 B 6 B 1 B 2 B 3 [入力例] 12 3 10 5 7 2 8 11 4 6 9 12 1 [出力例] 31 B 8 B 7 B 6 B 3 B 2 B 1 B 10 B 9 B 8 B 5 B 4 B 3 B 7 B 6 B 5 A 1 A 3 A 5 B 3 B 5 B 6 B 7 B 8 B 10 B 1 B 3 B 5 B 6 B 8 B 6 B 4 [入力例] 30 30 22 21 26 17 7 3 5 6 12 29 23 20 14 4 24 18 28 11 8 27 10 25 19 16 1 2 15 9 13 [出力例] 171 B 23 B 22 B 21 B 20 B 19 B 18 B 16 B 14 B 11 B 10 B 7 B 5 B 4 B 3 B 2 B 25 B 24 B 23 B 22 B 21 B 20 B 18 B 16 B 13 B 12 B 9 B 7 B 6 B 5 B 4 B 26 B 24 B 22 B 20 B 18 B 15 B 14 B 11 B 9 B 8 B 7 B 6 B 28 B 26 B 24 B 22 B 20 B 17 B 16 B 13 B 11 B 10 B 9 B 8 B 19 B 18 B 15 B 13 B 12 B 11 B 10 B 17 B 15 B 14 B 13 B 12 B 16 B 14 A 1 A 3 A 5 A 7 A 9 A 11 A 13 B 1 B 2 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 11 B 12 B 13 B 14 B 15 B 16 B 17 B 18 B 20 B 21 B 22 B 23 B 24 B 25 B 26 B 27 B 28 B 4 B 5 B 6 B 7 B 8 B 9 B 10 B 13 B 15 B 16 B 18 B 19 B 20 B 23 B 24 B 25 B 26 B 2 B 3 B 6 B 7 B 8 B 11 B 13 B 14 B 16 B 17 B 22 B 23 B 24 B 1 B 6 B 11 B 12 B 14 B 15 B 20 B 21 B 22 B 4 B 9 B 10 B 12 B 13 B 18 B 19 B 20 B 2 B 7 B 8 B 10 B 11 B 16 B 17 B 18 B 5 B 9 B 14 B 15 B 16 B 3 B 12 B 13 B 14 B 10 B 11 B 12 B 8 B 9 B 10 |
■参照サイト
AtCoder Regular Contest 147