C++の練習を兼ねて, AtCoder Beginner Contest 265 の 問題C (Belt Conveyor) ～ 問題D (Iroha and Haiku (New ABC Edition)) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 二分探索の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 265 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// 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--) char G[505][505]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[505]; scanf("%s", c); rep(j, W) G[i + 1][j + 1] = c[j]; } // 2. 判定. int ans = 250001, h = 1, w = 1; while(ans >= 0){ // 移動. // 上. if(G[h][w] == 'U'){ if(h > 1) --h; else break; } // 下. if(G[h][w] == 'D'){ if(h < H) ++h; else break; } // 左. if(G[h][w] == 'L'){ if(w > 1) --w; else break; } // 右. if(G[h][w] == 'R'){ if(w < W) ++w; else break; } // 次へ. --ans; } // 3. 出力. if(ans < 0) puts("-1"); else printf("%d %d\n", h, w); 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 |
[入力例] 2 3 RDU LRU [出力例] 1 3 ※AtCoderテストケースより [入力例] 2 3 RRD ULL [出力例] -1 ※AtCoderテストケースより [入力例] 9 44 RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR [出力例] 9 5 ※AtCoderテストケースより [入力例] 13 13 DRLURUDULULUD RDURRRDLULDUD DDLULDDDUUULL URRRUUDLRUDDD UDDUDUDRDURUD ULLUUDRUDRRLD RUULLRRDLURRL RUDDRRLDRDLUR ULDDLDURUDLRR RDULDRDUDDURL DRLLRDLDLLDRR DRRURDDLRLUDD RLULULRRDLURD [出力例] 13 9 [入力例] 20 22 RRDDLRDDDRUULUULUUDURU RDDUUDRUURLLRURRDDDRDU RRRDURLRURRLDUDLDDUULD ULUDLRLRLDRUDRRULLLLLL DDURDUDRDUDDRUDURDLLRL DRUDRDRRDDDRDLRULUUURU UUUUUDUURRDLDDRURUUURR URULDRULRLDUULDDURLRLR DDUDDRRLULRRDRRRDLURRD RURRRDRRDLLDLURDLRRUUR LLDUULLDLLURRULRRUURRU RURRDRULUUDRUDRUULDLUL URDRDLLLLLLRUDLULURLRD LUDDURRUULRDDRLDLDLRRU DDDLLULDUULRDURDUURUDU RDLLRULURDLRRURLLLUULD LLRLUDDLRULRUDLLUUULLL LRDLLLULURRLUULURDUDUD RRULLURDURLULDDULLDRRL URRDDRDRLLRRDUULLUULUR [出力例] 10 22 |
■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 |
// 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], aCum[202020]; int main(){ // 1. 入力情報. int N; LL P, Q, R; scanf("%d %lld %lld %lld", &N, &P, &Q, &R); rep(i, N){ scanf("%lld", &a[i]); aCum[i + 1] = aCum[i] + a[i]; } // 2. 整数の組 (x, y, z, w) が 存在するか？ bool ok = false; rep(x, N){ // x 固定で, y, z, w を 二分探索. int y = lower_bound(aCum, aCum + N + 1, aCum[x] + P) - aCum; if(aCum[y] == aCum[x] + P){ int z = lower_bound(aCum, aCum + N + 1, aCum[y] + Q) - aCum; if(aCum[z] == aCum[y] + Q){ int w = lower_bound(aCum, aCum + N + 1, aCum[z] + R) - aCum; if(aCum[w] == aCum[z] + R){ // printf("x=%d y=%d z=%d w=%d\n", x, y, z, w); ok = true; break; } } } // 見つかった. if(ok) break; } // 3. 出力. printf("%s\n", ok ? "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 |
[入力例] 10 5 7 5 1 3 2 2 2 3 1 4 3 2 [出力例] Yes ※AtCoderテストケースより [入力例] 9 100 101 100 31 41 59 26 53 58 97 93 23 [出力例] No ※AtCoderテストケースより [入力例] 7 1 1 1 1 1 1 1 1 1 1 [出力例] Yes ※AtCoderテストケースより [入力例] 30 54 34 115 2 20 18 6 10 7 13 19 5 2 2 1 4 1 7 12 11 9 10 19 14 2 1 19 11 8 15 13 8 16 [出力例] Yes [入力例] 50 643 1717 1465 85 36 103 63 57 91 43 73 92 39 90 120 70 101 57 43 112 81 110 56 35 47 81 109 32 58 42 32 61 53 39 129 120 73 105 58 110 118 117 39 35 124 118 89 81 112 56 105 69 56 [出力例] Yes [入力例] 100 113055 197583 92859 3000 5859 9713 4986 6390 3165 4257 406 3566 5806 7091 2479 1420 4926 5234 5853 640 1858 9214 5205 7140 8221 2341 2796 5028 7979 3501 4634 1465 1449 3154 5477 6106 5230 5150 3551 4105 1378 3680 6632 1846 6255 1391 8893 289 8644 5954 5458 7679 5956 8817 3139 7496 9426 8674 9610 9255 5522 4624 2792 267 1206 4782 6502 6373 1490 2723 8221 9605 455 5009 2388 4393 8570 3567 8716 1291 6662 399 915 6098 4766 9056 1549 7950 732 2770 7088 8544 2649 4141 3824 7346 746 2590 5027 5559 9925 1990 9955 [出力例] Yes |
■参照サイト
AtCoder Beginner Contest 265