C++の練習を兼ねて, 競プロ典型 90 問 の 問題008 (AtCounter) を解いてみた.
■感想.
1. 問題008は, 方針を決めるまでに苦労したものの, 動的計画法で行けそうに見えたので実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた(※本家の解説プログラムが, 汎用的に見え, 非常に勉強になったと思う).
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題008 を ご覧下さい.
■C++版プログラム(問題008／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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// 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 = 1e9 + 7; LL dpl[101010], dpr[101010], dp[101010]; int main(){ // 1. 入力情報. int N; char S[101010]; scanf("%d %s", &N, S); // 2. atc を 取り出す方法(dpl更新). LL a = 0, t = 0; rep(i, N){ // 前回分設定. dpl[i + 1] = dpl[i]; // 'a' が 出現した場合. if(S[i] == 'a') a++, a %= MOD; // 't' が 出現した場合. if(S[i] == 't') t += a, t %= MOD; // 'c' が 出現した場合. if(S[i] == 'c') dpl[i + 1] += t, dpl[i + 1] %= MOD; } // rep(i, N + 1) printf("%lld ", dpl[i]); // puts(""); // 3. der を 取り出す方法(dpr更新). LL e = 0, r = 0; repr(i, N - 1, 0){ // 前回分設定. dpr[i] = dpr[i + 1]; // 'r' が 出現した場合. if(S[i] == 'r') r++, r %= MOD; // 'e' が 出現した場合. if(S[i] == 'e') e += r, e %= MOD; // 'd' が 出現した場合. if(S[i] == 'd') dpr[i] += e, dpr[i] %= MOD; } // rep(i, N + 1) printf("%lld ", dpr[i]); // puts(""); // 4. atcoder を 取り出す方法(dp更新). rep(i, N){ // 前回分設定. dp[i + 1] = dp[i]; // 'o' が 出現した場合. if(i && S[i] == 'o'){ // 'o' よりも左側について, atc を 取り出す 方法は？ LL atc = dpl[i]; // 'o' よりも右側について, der を 取り出す 方法は？ LL der = dpr[i]; // 集計. dp[i + 1] += atc * der; dp[i + 1] %= MOD; } } // rep(i, N + 1) printf("%lld ", dp[i]); // puts(""); // 5. 出力. printf("%lld\n", dp[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 |
[入力例] 10 attcordeer [出力例] 4 ※AtCoderテストケースより [入力例] 41 btwogablwetwoiehocghiewobadegwhoihegnldir [出力例] 2 ※AtCoderテストケースより [入力例] 140 aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr [出力例] 279999993 ※AtCoderテストケースより [入力例] 18 eatstatcocdoeoderr [出力例] 56 [入力例] 50 ratfmdaiccdiotnclcdatcoktduoetsdeadmkrdxruwrxrsfkp [出力例] 264 [入力例] 100 zamtahacydohcrokatcoergatcloivatcbiorkxsgogudkedhserwrbedqeenoriuboncxdlexremderzoxakobiosbdzeqrhiyg [出力例] 8937 |
■参照サイト
008 – AtCounter