C++の練習を兼ねて, AtCoder Beginner Contest 258 の 問題C (Rotation) ～ 問題D (Trophy) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 258 解説 の 各リンク を ご覧下さい.
■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 |
// 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, Q; char c[505050]; scanf("%d %d %s", &N, &Q, c); // 2. クエリ回答. int cur = 0; rep(i, Q){ // 2-1. クエリ入力情報. int f, x; scanf("%d %d", &f, &x); // 2-2. クエリ 1. if(f == 1) cur = (cur + N - x) % N; // 2-3. クエリ 2. if(f == 2) printf("%c\n", c[(cur + x - 1) % N]); } 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 |
[入力例] 3 3 abc 2 2 1 1 2 2 [出力例] b a ※AtCoderテストケースより [入力例] 10 8 dsuccxulnl 2 4 2 7 1 2 2 7 1 1 1 2 1 3 2 5 [出力例] c u c u ※AtCoderテストケースより [入力例] 20 10 twlgmqdypwjtskihvnhv 1 10 2 17 2 16 1 18 1 4 1 4 1 14 2 9 2 13 1 11 [出力例] d q h l [入力例] 50 50 eoxymxbhxrrxqiqmajiezrxliivaassmgtjznemyamidozwsit 1 16 1 24 2 32 1 1 1 33 1 18 2 12 2 23 1 37 1 24 2 19 1 7 1 30 1 32 1 34 2 27 1 41 2 44 2 7 1 41 2 17 2 12 2 47 1 44 2 15 1 37 2 43 2 33 1 42 2 30 2 24 1 26 2 47 2 16 1 38 1 17 1 31 1 46 1 30 1 36 1 24 2 12 1 12 1 3 2 37 2 12 2 10 2 24 1 15 2 25 [出力例] m e s m z w r a l x g l i i q r a x q e z t z |
■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 |
// 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--) const LL INF = 2e18 + 1; // test_15.txt, test_17.txt で WA版だったため, 上限修正. LL a[202020], b[202020], aCum[202020], bCum[202020]; int main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); rep(i, N){ scanf("%lld %lld", &a[i], &b[i]); aCum[i + 1] = aCum[i] + a[i]; bCum[i + 1] = bCum[i] + b[i]; } // 2. 必要時間の最小値は？ LL ans = INF, bMin = INF; repx(i, 1, N + 1){ if(X < i) break; bMin = min(bMin, b[i - 1]); ans = min(ans, aCum[i] + bCum[i] + (X - i) * bMin); } // 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 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 |
[入力例] 3 4 3 4 2 3 4 2 [出力例] 18 ※AtCoderテストケースより [入力例] 10 1000000000 3 3 1 6 4 7 1 8 5 7 9 9 2 4 6 4 5 1 3 1 [出力例] 1000000076 ※AtCoderテストケースより [入力例] 5 7 1 17 11 12 29 16 20 8 27 18 [出力例] 101 [入力例] 10 9 4 13 100 36 66 20 92 78 41 62 24 76 13 54 78 94 10 97 9 1 [出力例] 121 [入力例] 25 20220703 8670 17591 7289 13540 5610 8149 8480 17433 9439 12167 8259 10501 9514 15404 12525 10569 10265 5987 5874 10185 8052 13993 14753 6198 14788 8419 9944 6501 13658 10491 5487 5826 6070 6662 5985 13730 9525 6683 6377 5877 8918 14170 7335 8392 12388 3030 11943 4040 13716 5050 [出力例] 61269101103 |
■参照サイト
AtCoder Beginner Contest 258