C++の練習を兼ねて, AtCoder Beginner Contest 242 の 問題C (1111gal password) ~ 問題D (ABC Transform) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題Cで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 問題Dで, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 242 解説 の 各リンク を ご覧下さい.
■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 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--) const LL MOD = 998244353; LL dp[10], pd[10]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 初期化. repx(j, 1, 10) pd[j] = 1; // 3. dp更新. repx(i, 1, N){ // 初期化. repx(j, 1, 10) dp[j] = 0; // 今回分更新. repx(j, 1, 10){ // 桁の数字が, 1 小さい. if(j > 1){ dp[j - 1] += pd[j]; dp[j - 1] %= MOD; } // 桁の数字が, 1 大きい. if(j < 9){ dp[j + 1] += pd[j]; dp[j + 1] %= MOD; } // 桁の数字が, 等しい. dp[j] += pd[j]; dp[j] %= MOD; } // 前回分更新. repx(j, 1, 10) pd[j] = dp[j]; } // 4. 集計. LL ans = 0; repx(j, 1, 10){ ans += dp[j]; ans %= MOD; } // 5. 出力. 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 |
[入力例] 4 [出力例] 203 ※AtCoderテストケースより [入力例] 2 [出力例] 25 ※AtCoderテストケースより [入力例] 1000000 [出力例] 248860093 ※AtCoderテストケースより [入力例] 3 [出力例] 71 [入力例] 5 [出力例] 583 [入力例] 2022 [出力例] 660740445 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc242/editorial/3520 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<LL, LL, LL>; #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. 入力情報. char x[101010]; scanf("%s", x); string S(x); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, LL t, LL k, LL d) -> T3 { // 終了条件(t = 0). if(!t) return {0, k, d}; // 終了条件(k = 0). if(!k) return {t, 0, d}; // 再帰処理. return self(self, t - 1, k / 2, d + 1 + (k % 2)); }; // 3. クエリ回答. int Q; scanf("%d", &Q); rep(i, Q){ // クエリ入力情報. LL t, k; scanf("%lld %lld", &t, &k); // 変化分. T3 p = dfs(dfs, t, k - 1, 0); LL a = get<0>(p); LL b = get<1>(p); LL c = get<2>(p); // printf("t=%lld k=%lld a=%lld b=%lld c=%lld\n", t, k, a, b, c); // 出力. LL d = a ? (LL)(S[0] - 'A' + a + c) : (LL)(S[(int)b] - 'A' + c); printf("%c\n", (int)(d % 3) + 'A'); } 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 |
[入力例] ABC 4 0 1 1 1 1 3 1 6 [出力例] A B C B ※AtCoderテストケースより [入力例] CBBAACCCCC 5 57530144230160008 659279164847814847 29622990657296329 861239705300265164 509705228051901259 994708708957785197 176678501072691541 655134104344481648 827291290937314275 407121144297426665 [出力例] A A C A A ※AtCoderテストケースより [入力例] ACBCA 10 0 1 0 3 1 1 1 5 2 2 2 13 3 1 3 15 3 26 3 38 [出力例] A B B C A B A B A C [入力例] BBCAABCBCA 20 0 2 0 5 0 9 1 3 1 7 1 17 2 1 2 10 2 25 3 30 3 50 3 77 4 55 4 111 5 22 5 320 6 88 6 123 6 333 7 1111 [出力例] B A C C B A A C B C A B A A A B C C A B |
■参照サイト
AtCoder Beginner Contest 242