C++の練習を兼ねて, AtCoder Beginner Contest 202 の 問題C (Made Up) ~ 問題D (aab aba baa) を解いてみた.
■感想.
1. 問題Dは, 動的計画法が使えそうに見えたので, 実装してみたところ, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 問題Dは, 動的計画法を使いながら, 文字列を確定させていく処理が, 個人的には, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 202 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) int a[101010], b[101010], c[101010]; LL bc[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); rep(i, N){ scanf("%d", &c[i]); c[i]--; } // 2. b[c[j]] を 保存. rep(i, N) bc[b[c[i]]]++; // 3. 条件を満たす 整数の組(i, j) を 計算. LL ans = 0; rep(i, N) ans += bc[a[i]]; // 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 |
[入力例] 3 1 2 2 3 1 2 2 3 2 [出力例] 4 ※AtCoderテストケースより [入力例] 4 1 1 1 1 1 1 1 1 1 2 3 4 [出力例] 16 ※AtCoderテストケースより [入力例] 3 2 3 3 1 3 3 1 1 1 [出力例] 0 ※AtCoderテストケースより [入力例] 20 10 1 3 9 12 12 11 12 6 5 12 3 10 1 3 7 10 6 7 2 8 1 6 7 3 2 12 8 10 10 8 11 1 11 1 12 10 11 11 6 11 1 1 4 9 2 7 10 7 7 2 12 1 8 4 9 10 9 5 1 [出力例] 39 [入力例] 100 21 21 14 17 15 19 11 21 4 14 5 18 15 19 3 4 13 10 4 18 20 22 21 14 14 19 17 18 19 5 15 5 10 3 17 10 2 12 15 16 9 19 2 5 19 15 9 9 10 11 10 5 16 18 1 7 17 4 2 13 18 17 18 6 16 9 7 1 14 18 10 10 3 18 18 1 7 18 22 22 7 18 4 3 2 13 20 16 3 18 19 16 2 20 18 17 8 10 8 19 13 22 13 18 15 20 1 20 18 8 21 6 1 3 18 12 4 8 1 17 12 8 1 5 16 10 2 3 14 16 2 21 20 11 6 8 5 17 10 5 2 8 1 10 21 18 18 10 21 22 22 6 3 19 22 7 13 14 7 20 6 12 7 20 6 22 15 14 8 22 3 7 19 21 16 5 15 22 7 20 11 2 7 9 22 10 16 7 20 12 13 6 20 17 19 8 22 21 13 6 4 11 18 9 11 3 16 22 1 15 3 13 1 21 7 15 11 9 22 10 14 14 17 15 2 22 12 1 16 4 17 2 21 15 19 11 3 19 9 5 7 4 13 19 17 11 22 22 15 9 14 14 2 19 13 13 16 13 18 6 7 14 7 22 7 18 17 18 21 10 13 10 22 8 11 4 18 3 15 7 6 11 17 16 19 10 18 9 13 21 3 8 2 2 20 3 12 10 15 11 [出力例] 455 |
■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 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// 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--) #define pb push_back LL C[61][61]; LL dp[66][2]; // i番目を, 'a', 'b' のいずれを設定するか保存. int main(){ // 1. 入力情報. int A, B; LL K; scanf("%d %d %lld", &A, &B, &K); // 2. パスカルの三角形で, 事前計算. rep(i, 61){ rep(j, 61){ if(!j || j == i) C[i][j] = 1LL; else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } // rep(i, 20){ // rep(j, 20) printf("%lld ", C[i][j]); // puts(""); // } // 3. dp更新. string ans = ""; int resA = A, resB = B; dp[0][0] = 1; dp[0][1] = 1 + C[resA + resB - 1][resB]; repx(i, 1, A + B + 1){ // 3-1. 前回分取得. if(dp[i - 1][1] <= K){ dp[i][0] = dp[i][1] = dp[i - 1][1]; ans.pb('b'); resB--; }else{ dp[i][0] = dp[i][1] = dp[i - 1][0]; ans.pb('a'); resA--; } assert(resA >= 0); assert(resB >= 0); // 3-2. i番目が, 'b' となる場合の開始番号. dp[i][1] += C[resA + resB - 1][resB]; } // rep(i, 10) printf("%lld %lld\n", dp[i][0], dp[i][1]); // 4. 出力. 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 |
[入力例] 2 2 4 [出力例] baab ※AtCoderテストケースより [入力例] 30 30 118264581564861424 [出力例] bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa ※AtCoderテストケースより [入力例] 3 2 5 [出力例] ababa [入力例] 1 1 1 [出力例] ab [入力例] 1 1 2 [出力例] ba [入力例] 1 3 4 [出力例] bbba [入力例] 5 3 25 [出力例] abaababa [入力例] 10 17 1234567 [出力例] abaabbabbabbabbbababbbbbaba [入力例] 25 11 123456789 [出力例] aaaabbababaabaaaabbaaaaabaaabaabbaaa |