問題
解法
?
があると複雑なため、まずは ?
抜きで考えてみる。
素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) using ll = long long; int main() { string s; cin >> s; int n = s.size(); ll ans = 0; REP(i,n) { for(int j=i+1; j<n; j++) { for(int k=j+1; k<n; k++) { ans += (s[i]=='A' && s[j]=='B' && s[k]=='C'); } } } cout << ans << endl; }
$O(N{^3})$ では制約に間に合わないためDPで考えてみる。
dp[n][4]; // [n文字までで][1: Aまで, 2: Bまで, 3: Cまでを満たす状態]
ll dp[100000][4]; int main() { string s; cin >> s; int n = s.size(); dp[0][0] = 1; REP(i,n) { REP(j,4) dp[i+1][j] += dp[i][j]; // i+1の各状態にiの状態の数をそのまま足す if (s[i] == 'A') dp[i+1][1] += dp[i][0]; // Aにすすめる else if (s[i] == 'B') dp[i+1][2] += dp[i][1]; // Bにすすめる else if (s[i] == 'C') dp[i+1][3] += dp[i][2]; // Cにすすめる } cout << dp[n][3] << endl; }
?
の場合を考慮する。
// mint にする mint dp[100000][4]; int main() { string s; cin >> s; int n = s.size(); dp[0][0] = 1; REP(i,n) { REP(j,4) dp[i+1][j] += s[i]== '?' ? dp[i][j]*3 : dp[i][j]; // ?の場合は3文字ありえる if (s[i] == 'A') dp[i+1][1] += dp[i][0]; else if (s[i] == 'B') dp[i+1][2] += dp[i][1]; else if (s[i] == 'C') dp[i+1][3] += dp[i][2]; else if (s[i] == '?') { // ? の場合はA, B, C それぞれ考慮する dp[i+1][1] += dp[i][0]; dp[i+1][2] += dp[i][1]; dp[i+1][3] += dp[i][2]; } } cout << dp[n][3] << endl; return 0; }
雑感
DPムズい