C++の練習を兼ねて, AtCoder Regular Contest 152 の 問題A (Seat Occupation) ~ 問題B (Pass on Path) を解いてみた.
■感想.
1. 問題A, B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題B で, 尺取り法 の 復習ができたので 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 152 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc152/editorial/5100 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int main(){ // 1. 入力情報. int N, L; scanf("%d %d", &N, &L); // 2. 解説通り. int k = 0, a; rep(i, N){ scanf("%d", &a); if(a == 2) k = i + 1; } // 3. 出力. printf("%s\n", (2 * k <= N + 1) ? "Yes" : "No"); 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 |
[入力例] 2 4 2 2 [出力例] No ※AtCoderのテストケースより [入力例] 3 4 1 2 1 [出力例] Yes ※AtCoderのテストケースより [入力例] 5 7 2 1 2 1 1 [出力例] Yes [入力例] 5 7 1 1 1 2 2 [出力例] No [入力例] 8 11 2 1 2 2 1 1 1 1 [出力例] Yes [入力例] 17 23 1 1 1 1 1 1 1 2 2 1 2 2 2 1 1 1 2 [出力例] No [入力例] 100 115 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 [出力例] Yes |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc152/editorial/5101 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) LL a[202020]; int main(){ // 1. 入力情報. int N; LL L; scanf("%d %lld", &N, &L); rep(i, N) scanf("%lld", &a[i]); // 2. 尺取り法(解説通り). LL ans = 202020202020202020; LL r = N - 1; rep(l, N){ // l, r を 見つける. LL d = abs(a[l] - (L - a[r])); repr(i, r, l){ if(d < abs(a[l] - (L - a[i]))) break; d = abs(a[l] - (L - a[i])); r = i; } // 最小値更新. ans = min(ans, 2 * L + 2 * d); } // 3. 出力. 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 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 |
[入力例] 2 6 2 5 [出力例] 14 ※AtCoderのテストケースより [入力例] 2 3 1 2 [出力例] 6 ※AtCoderのテストケースより [入力例] 6 16 2 7 8 11 15 16 [出力例] 32 [入力例] 10 55 12 13 17 21 23 31 33 35 39 50 [出力例] 112 [入力例] 20 125 21 33 40 51 57 60 61 66 71 76 87 88 91 93 97 101 102 109 111 115 [出力例] 252 [入力例] 50 2022 303 314 318 333 349 352 369 475 493 506 532 536 537 545 571 608 636 663 702 704 744 767 817 854 873 877 922 981 999 1053 1092 1093 1094 1151 1184 1196 1214 1238 1268 1273 1297 1301 1304 1326 1347 1389 1392 1404 1409 1410 [出力例] 4048 [入力例] 100 20221123 128835 562377 897048 1152450 1199393 1529218 1726509 1913983 2864404 2895053 2926150 3099197 3268192 3681471 3964738 4154313 4508141 4555753 4590559 4744276 4817919 4897461 5277397 5356400 5710006 5936848 6152387 6205833 6263672 6365982 6516841 6602161 6694602 6828548 6972057 7492155 7598137 7821736 7861994 8241001 8268328 8320758 8383872 9171490 9315253 9455053 9606984 9719161 9935027 10149081 10876706 10885955 10897725 10958945 11093741 11206593 11310413 11313808 11534793 11581603 11674632 11894174 11894642 12047576 12074845 12122608 12156598 12435718 12547534 12830845 12891461 13589452 14020667 14034695 14110691 14121735 14351669 14429505 14645628 15004934 15306849 15904377 16201626 16274361 16418629 16871621 16926232 16992253 17197178 18064919 18335010 18344733 18487232 18736047 18877809 19062531 19188601 19794983 19964528 20141094 [出力例] 40453000 [入力例] 250 314159265 9112972 9410829 9743615 11117859 11410003 11563552 12790573 12847345 13673853 13723022 18128097 21179986 21765253 25885744 26655258 29434614 30498934 30565072 31005545 32904736 33291363 33638067 36843825 37484998 39120342 39578010 41276473 42073898 42132396 42205626 42565822 43934228 45788734 45883163 47072579 47608190 48265188 49994174 61682393 62254104 64085415 64229602 64629536 64766735 66871613 68500814 72411276 72481705 72713086 73500005 73582728 74413292 74445316 79695650 82434775 86201587 87744748 88287560 89645968 89684376 90475385 92318594 93643604 95113684 95237729 96049566 96147279 98700156 99041712 99177717 99183984 100783911 101792441 104017323 104027336 104462341 105172235 105290064 108489733 108505278 109026346 109544104 109642592 110788725 110938708 112853720 115013139 117818948 117832475 119787009 120252090 120588494 123472619 123868296 124696017 125356818 125758804 128265366 128400070 130759244 130941323 133233782 135666494 136462099 136578583 137748879 139203836 139797385 141806181 142316105 144680092 145739024 146259225 146857258 148137376 150721159 150780241 150913094 153198200 154123816 154553304 155814954 156538992 156848921 160434739 160819712 162192909 162590128 163274291 163437259 165392437 165563440 165628358 165915439 166382456 167249880 171398471 171559795 171999154 172359846 173195723 175082168 175351537 175557970 176557034 176558208 177264997 177576723 180431386 180659553 182621904 182827207 183065558 183318911 183624887 183974582 184183073 186031061 186050200 191921747 194167703 195246383 195894239 200000536 200186882 200945686 205519593 210161050 211401051 213541610 220132394 227354612 227555002 228828979 229680455 230449950 231426845 237168219 237757594 237979552 238378360 238381351 238612590 238787941 239593125 241313174 243256000 245521314 247658929 248240712 249565805 252830182 253517441 255011300 256235525 258018692 260614119 262953868 263240697 263674422 264525063 264947133 268120373 268131263 268785676 268953364 270897923 271367636 271887314 273392330 274928749 275477763 275489407 276457472 277332334 281025034 281645511 281682352 283350413 283747258 283803716 284535582 285007014 285356826 285407404 285946677 287551595 287585907 288459663 288565068 290742246 290822735 291769684 293202209 293915634 294308274 295633185 296082485 296404123 296863402 300533964 302004624 302621960 302859845 304395456 305599692 305681614 306177876 308900855 310310310 [出力例] 628320224 |
■参照サイト
AtCoder Regular Contest 152