n度あることはn+1度ある

書きたいことを書く 統一性はない

ABC104 D - We Love ABC

DPが本当に苦手なので解説も放送も野良解説も訳がわからなく苦労した問題。
i番目の文字に対して以下の情報を保存しながらDPします
0. i番目までで1つも文字を選ばない組み合わせ
1. i番目までで"A"までを選ぶ組み合わせ
2. i番目までで"AB"までを選ぶ組み合わせ
3. i番目までで"ABC"までを選ぶ組み合わせ
i番目の文字が'A'だったとき、上記の1の要素を増やすことができます。それ以外は不変です。どれだけ増えるかというと、i-1番目の0の要素の数だけです。
BとCの場合も同様に考えることができます。
次にi番目の文字が'?'だったときは、二通りの増やし方ができます。
1つ目は、'?'が'ABC'の文字を担って"ABC"を構築しようとするときです。このときは、A,B,Cと同じ考え方で大丈夫です。
2つ目は、'?'が文字の構築に関与しないときです。これはA,B,Cの3つがはいるため、i-1番目のそれぞれの要素を3倍して加算してやればよいです。
具体例を考えます。入力例1のA??Cの場合、DPの遷移は以下のようになります。
A
0. 1
1. 1
2. 0
3. 0
0. Aを選ばないときの1通り
1. このAから文字列を構築し始める場合の1通り
?
0. 3
1. 4
2. 1
3. 0
0. AA、AB、AC、のときにこれらの文字列から文字の構築をしない場合の3通り
1. この?を文字の構築に考慮させず、最初のAで文字を作り始めるときの3通り+最初のAを考慮せずこの?をAにして、文字を作り始める1通り
2. ?をBに割り当てて作る1通り
?
0. 9
1. 15
2. 7
3. 1
0. この?をA,B,Cにしたとき(前の0の3倍)
1. この?を文字の構築に考慮させない場合(前の三倍)+前の2文字を考慮せず、この?で文字を作り始める場合(前の0番目の要素)
以下略
C
0. 9
1. 15
2. 7
3. 8
こんな感じで、最後のdp[N][3]に解がでます。
DP云々っていうよりも数学の組み合わせの問題という面が強いような気がします。このあたりの分野もすごく苦手なのでなんとかしたいです。

#include <bits/stdc++.h>
using namespace std;
#define INF (long)(1e9+7)
int main(){
    string s; cin>>s;
    vector<long[4]> dp(s.size()+1); 
    dp[0][0]=1;
    for(int i=1;i<=s.size();i++){
        for(int j=0;j<=3;j++){
            dp[i][j]=dp[i-1][j];
            if(s[i-1]=='?')
                dp[i][j]*=3;
            dp[i][j]%=INF;
        }
        if(s[i-1]!='?')
            dp[i][s[i-1]+1-'A']+=dp[i-1][s[i-1]-'A'];
        else{
            for(int j=1;j<=3;j++){
                dp[i][j]+=dp[i-1][j-1];
               dp[i][j]%=INF;
            }
        }
    }
    cout<<dp[s.size()][3]%INF;
}   

参考:
AtCoder Beginner Contest 104 - Unhappy Go Lucky!