C++の練習を兼ねて, AtCoder Beginner Contest 261 の 問題C (NewFolder(1)) ～ 問題D (Flipping and Bonus) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 261 解説 の 各リンク を ご覧下さい.
■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 |
// 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; scanf("%d", &N); // 2. 出力. map<string, int> m; rep(i, N){ char c[22]; scanf("%s", c); string s(c); ++m[s]; string ans = s; if(m[s] > 1) ans += "(" + to_string(m[s] - 1) + ")"; printf("%s\n", ans.c_str()); } 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 |
[入力例] 5 newfile newfile newfolder newfile newfolder [出力例] newfile newfile(1) newfolder newfile(2) newfolder(1) ※AtCoderテストケースより [入力例] 11 a a a a a a a a a a a [出力例] a a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10) ※AtCoderテストケースより [入力例] 10 abc abc arc abc arc agc abc arc agc ahc [出力例] abc abc(1) arc abc(2) arc(1) agc abc(3) arc(2) agc(1) ahc |
■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 |
// 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 dp[5050][5050], x[5050], b[5050]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &x[i + 1]); rep(i, M){ int c; LL y; scanf("%d %lld", &c, &y); b[c] = y; } // 2. dp更新. repx(i, 1, N + 1){ rep(c, i){ // 表. dp[i][c + 1] = max(dp[i][c + 1], dp[i - 1][c] + x[i] + b[c + 1]); // 裏. dp[i][0] = max(dp[i][0], dp[i - 1][c]); } } // 3. 最大値は？ LL ans = 0; rep(j, N + 1) ans = max(ans, dp[N][j]); // 4. 出力. 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 |
[入力例] 6 3 2 7 1 8 2 8 2 10 3 1 5 5 [出力例] 48 ※AtCoderテストケースより [入力例] 3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000 [出力例] 5000000000 ※AtCoderテストケースより [入力例] 3 2 3 5 2 1 3 3 7 [出力例] 20 [入力例] 15 10 20 2 14 1 3 18 16 25 22 1 10 9 16 15 8 1 11 3 10 4 12 5 10 6 11 7 36 8 37 9 59 11 64 12 54 [出力例] 493 [入力例] 50 30 48 76 39 78 249 156 152 209 110 176 216 226 77 104 41 141 69 23 169 79 180 237 28 213 235 156 101 63 198 47 106 76 205 160 201 63 140 164 181 12 45 38 142 179 45 188 258 136 252 125 1 45 3 132 5 189 6 129 7 97 9 216 11 36 12 89 14 221 16 205 18 158 19 121 21 315 23 65 24 109 26 340 27 101 28 187 30 606 32 686 34 941 35 488 36 675 38 431 40 2022 42 1824 44 1296 45 1958 46 1709 47 1447 [出力例] 23456 |
■参照サイト
AtCoder Beginner Contest 261