C++の練習を兼ねて, AtCoder Beginner Contest 234 の 問題F (Reordering) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 数え上げする種類数が, アルファベットの出現数にのみ依存するという部分が, 不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 234 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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/abc234/editorial/3223 // 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 C[5050][5050], dp[27][5050]; int freq[26]; int main(){ // 1. 入力情報. char s[5050]; scanf("%s", s); string S(s); int N = S.size(); // 2. 出現数('a' ～ 'z'). rep(i, N) rep(j, 26) freq[j] = freq[j] + (S[i] == ('a' + j)); // 3. パスカルの三角形. C[0][0] = 1; repx(i, 1, 5050){ rep(j, 5050){ C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j]; C[i][j] %= MOD; } } // 4. dp更新(index注意, j は 0 ～ N までの範囲を動くとのこと). dp[0][0] = 1; rep(i, 26){ rep(j, N + 1){ rep(k, min(j, freq[i]) + 1){ dp[i + 1][j] += dp[i][j - k] * C[j][k]; dp[i + 1][j] %= MOD; } } } // 5. 集計. LL ans = 0; repx(j, 1, N + 1) ans += dp[26][j], ans %= MOD; // 6. 出力. 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 |
[入力例] aab [出力例] 8 ※AtCoderテストケースより [入力例] aaa [出力例] 3 ※AtCoderテストケースより [入力例] abcdefghijklmnopqrstuvwxyz [出力例] 149621752 ※AtCoderテストケースより [入力例] abc [出力例] 15 [入力例] abracadabra [出力例] 257589 [入力例] jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol magicalspell [出力例] 985106188 |
■参照サイト
AtCoder Beginner Contest 234