C++の練習を兼ねて, AtCoder Beginner Contest 104 の 問題D (D – We Love ABC) を解いてみた.
■感想.
1. 問題D は, DPを使うと思って解答しようとしたが, 方針がまとまらず, 解説を見て, 解き直したものである.
※なお, 問題C は, 難しすぎたので, 正解者のソースを勉強する方針に切り替え, 自力での解答は放棄している.
本家のサイトABC 104 Editorialをご覧下さい.
■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 |
// 解き直し. // ABC 104 Editorial // https://img.atcoder.jp/abc104/editorial.pdf #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 動的計画法(DP)の適用(解説通り). LL l = S.size(); LL dp[l + 1][4] = {}; dp[l][3] = 1; dp[l][2] = 0, dp[l][1] = 0, dp[l][0] = 0; for(int i = l - 1; i >= 0; i--){ char c = S[i]; for(int j = 3; j >= 0; j--){ if(j == 3){ if(c == '?') dp[i][j] = 3 * dp[i + 1][j], dp[i][j] %= MOD; else dp[i][j] = 1 * dp[i + 1][j], dp[i][j] %= MOD; } if(j < 3){ if(c == '?'){ dp[i][j] = 3 * dp[i + 1][j]; dp[i][j] %= MOD; dp[i][j] += 1 * dp[i + 1][j + 1]; dp[i][j] %= MOD; }else{ string ABC = "ABC"; dp[i][j] = 1 * dp[i + 1][j]; dp[i][j] %= MOD; if(c == ABC.substr(j, 1)[0]) dp[i][j] += 1 * dp[i + 1][j + 1], dp[i][j] %= MOD; } } } } // 3. 出力 ～ 後処理. cout << dp[0][0] << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 104