AtCoder Beginner Contest 122 - 競プロやります。

C - GeT AC
- 方針
- ソースコード
D - We Like AGC

C - GeT AC

https://atcoder.jp/contests/abc122/tasks/abc122_c

方針

index は 0 始まりとします。
0 文字目から n 文字目までに含まれる 'AC' の数を $f(n)$ とすると、 $l$ 文字目から $r$ 文字目までに含まれる 'AC' の数は $f(r) - f(l)$ で表されます。あらかじめ $n = 0, 1, \dots |S| - 1$ について $f(n)$ を求めておくと、各クエリに対して $O(1)$ で答えを出すことが出来ます。

ここでクエリに対する答えは $f(r)-f(l)$ であって、 $f(r) - f(l-1)$ ではないです。これは $l-1$ 文字目が A で $l$ 文字目が C である場合を除くためです。

$f(n)$ を求めるには、あらかじめ $f(n) = 0$ と初期化しておき、 i 文字目と i-1 文字目で 'AC' が作られるときに $f(i) = 1$ とします。最後に $f(n)$ の累積和を取ればよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, Q;  string S;
    cin >> N >> Q >> S;
    int L = S.length();
    vector<int> f(L,0);
    
    for(int i=1; i<L; i++){
        if(S[i-1]=='A' && S[i]=='C'){
            f[i] = 1;
        }
    }
    for(int i=1; i<L; i++) f[i] += f[i-1];

    vector<int> l(Q,0), r(Q,0);
    for(int i=0; i<Q; i++) {
        cin >> l[i] >> r[i];
        l[i]--;  r[i]--;
    }
    for(int i=0; i<Q; i++){
        cout << f[r[i]] - f[l[i]] << endl;
    }
}

D - We Like AGC

https://atcoder.jp/contests/abc122/tasks/abc122_d

方針

以下では 'A', 'G', 'C', 'T' のみから成る文字列のみを考えます。このもとで、

"AGC" を含まない
隣り合う2文字の入れ替えによっても "AGC" を含まない

の２条件を満たす文字列の数を数えます。

この条件はより具体的には、文字列の中に以下を含まないことと同じです：

?ACG
?AGC
?GAC
A?GC
AG?C

ここで ? はA,G,C,T の中の任意の 1 文字です。よって末尾の 3 文字がわかれば、次に付け加えることの出来る文字が決まります。

　 $dp[i][j][k][n] =$ (長さ $n$ の文字列のうち、末尾 3 文字が左から順に $i, j, k$ であるようなものの数)
とします。ただし $i, j, k = 0, 1, 2, 3$ を、それぞれ A, G, C, T に対応させます。例えば、 $dp[0][3][2][n]$ は、末尾が 'ATC' であるような長さ $n$ の文字列の数です。
求めたいものは、 $\displaystyle \sum_{i,j,k=0}^{3} dp[i][j][k][N]$ となります。

まず入力例 1 より長さ 3 の場合は "AGC", "ACG", "GAC" のみが禁止されます。よって、
$\displaystyle dp[i][j][k][3] = \begin{cases} 0~( (j,k,l)=(0,1,2),(0,2,1),(1,0,2) ) \\ 1~(\text{else}) \end{cases}$
となります(上記以外のすべての dp は、あらかじめ 0 で初期化されているものとします)。

次に $dp[i][j][k][n]$ がわかっているときの $dp[i][j][k][n+1]$ の求め方を考えます。

(1) 末尾 3 文字が "?AC" のとき
$i = \text{(任意)},~j=0,~k=2$ の場合に対応します。
このとき次の 1 文字として G 以外を用いることが出来ます。よって、
　 $dp[j][k][l][n+1] += dp[i][j][k][n]~(l=0,2,3)$
とすることが出来ます。
ここで状態 (i, j, k) に 1 文字追加するので、次の状態は (j, k, (次の文字)) となります。次の文字は G 以外なので $l = 0,2,3$ です。

(2) 末尾 3 文字が "?AG", "?GA", "A?G", "AG?" のとき
文字列と $(i, j, k)$ は以下のように対応します：
　"?AG" ⇔ $(\text{任意}, 0, 1)$
　"?GA" ⇔ $(\text{任意}, 1, 0)$
　"A?G" ⇔ $(0, \text{任意}, 1)$
　"AG?" ⇔ $(0, 1, \text{任意})$

このとき次の 1 文字として C 以外を用いることが出来ます。よって、
　 $dp[j][k][l][n+1] += dp[i][j][k][n]~(l=0,1,3)$
とできます。

(3) 上記以外のとき
このときは次の 1 文字として任意の文字を使えます。よって、
　 $dp[j][k][l][n+1] += dp[i][j][k][n]~(l=0,1,2,3)$
とできます。

以上の関係を用いて、 $n = 3$ から $n=N$ まで順に $dp[i][j][k][n]$ を求めていけばよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;  cin >> N;
    int M = 1e9+7;
    vector<int> dp[4][4][4];
    for(int i=0; i<4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++){
        dp[i][j][k] = vector<int>(N+1, 0);
    }

    // 長さ 3 の文字列は AGC, ACG, GAC 以外が許される。
    for(int i=0; i<4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++){
        if(!((i==0 && j==1 &&k==2)||(i==1 && j==0 && k==2)||(i==0 && j==2 && k==1))){
            dp[i][j][k][3] = 1;
        }
    }

    for(int n=3; n<N; n++){
        for(int i=0; i<4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++){
            if(j==0 && k==2){
                // ?AC の後ろには G 以外が入る
                dp[j][k][0][n+1] = (dp[j][k][0][n+1] + dp[i][j][k][n])%M;
                dp[j][k][2][n+1] = (dp[j][k][2][n+1] + dp[i][j][k][n])%M;
                dp[j][k][3][n+1] = (dp[j][k][3][n+1] + dp[i][j][k][n])%M;
            }else if((i==0 && k==1) || (i==0 && j==1) || (j==0 && k==1) || (j==1 && k==0)){
                // A?G, AG?, ?AG, ?GA の後ろには C 以外が入る
                dp[j][k][0][n+1] = (dp[j][k][0][n+1] + dp[i][j][k][n])%M;
                dp[j][k][1][n+1] = (dp[j][k][1][n+1] + dp[i][j][k][n])%M;
                dp[j][k][3][n+1] = (dp[j][k][3][n+1] + dp[i][j][k][n])%M;
            }else {
                // 上記以外は n+1 文字目としてなんでも使える
                for(int m=0; m<4; m++){
                    dp[j][k][m][n+1] = (dp[j][k][m][n+1] + dp[i][j][k][n])%M;
                }
            }
        }
    }

    int ret = 0;
    for(int i=0; i<4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++){
        ret = (ret + dp[i][j][k][N])%M;
    }
    cout << ret << endl;
}

反省

はじめは "AGC", "GAC", "ACG" を含まない文字列を数えればよいと考え、サンプル 2 (N=4)で詰まりました。この間違いは具体的に N=4 の場合の文字列を書き出すことで気づくことが出来ました。

そうして上記の方針に修正できたのですが、dp テーブルを dp[64][N] と持ってしまったせいで、遷移を考えるときに複雑になり、延々とバグらせてしまいました。扱いやすい実装って大事ですね。