【ABC122】D - We Like AGC
解法
3つの条件を上から順に条件1、条件2、条件3と呼ぶことにする。
3つ目の条件が存在しない場合、次のDPで解くことができる。
dp[i][j][k] ← 長さiでi-1文字目がj、i文字目がkであるような条件1,2を満たす文字列はいくつあるか
遷移をする際には、i + 1文字目に追加する文字列をcとすると、
- j = 'A', k = 'G', c = 'C' であるとき
- 部分文字列に'AGC'を含むため、遷移しない
- それ以外のとき
- dp[i+1][k][c] ← dp[i+1][k][c] + dp[i][j][k]
ただしこの問題では、隣接する文字をスワップした場合に、条件1,2を満たさない文字列は排除しないといけないため、このDPを改良する必要がある。
上のDPでは、末尾3文字の並びがどうなっているかによって遷移の仕方を変えていたので、改良するに当たって、条件1,2を満たし、条件3を満たさないような末尾の文字列の並び方にどのようなものがあるかを考える。
すると、下のようなパターンがあることがわかる。
- 末尾3文字の文字列が条件3だけ満たさないとき
- サンプル1の解説を見るとわかるが、'ACG'と'GAC'が該当する
- 末尾4文字の文字列が条件3だけ満たさず、'ACG'と'GAC'を含まないとき
- 任意の文字を＊と表現すると、'A＊GC'と'AG＊C'が該当する
- 末尾5文字以上の文字列が条件3だけ満たさず、'ACG'、'GAC'、'A＊GC'、'AG＊C'を含まないとき
ということで、末尾4文字の並びがどうなっているかを状態に持つDPをすれば解けることがわかった。
定義は、
dp[i][j][k][l] ← 長さiでi-2文字目がj、i-1文字目がk、i文字目がlであるような条件1~3を満たす文字列はいくつあるか
遷移をする際には、i + 1文字目に追加する文字列をcとすると、
- 'AGC'、'ACG'、'GAC'、'A＊GC'、'AG＊C'が末尾に含まれるとき
- 条件1~3を満たさないため、遷移しない
- それ以外の場合
- dp[i+1][k][l][c] ← dp[i+1][k][l][c] + dp[i][j][k][l]
初期化する際には、少し注意が必要で、'T'が条件に影響を及ぼさないことを利用し、
dp[0]['T']['T']['T'] ← 1
としておく。
すべての遷移が終了後、j, k, lを全探索し、dp[N][j][k][l]を集計すれば答えを得ることができる。
実装
void solve(long long N){ // dpテーブル vector<vector<vector<vector<mint>>>> dp(N+1, vector<vector<vector<mint>>> (4, vector<vector<mint>>(4, vector<mint>(4, 0)))); // 文字とインデックス番号の対応付け vector<char> c = {'A', 'C', 'G', 'T'}; // 無害なTで初期化 dp[0][3][3][3] = 1; REP (i, N) { REP (j, 4) { REP (k, 4) { REP (l, 4) { REP (m, 4) { // AGC if (k == 0 && l == 2 && m == 1) continue; // ACG if (k == 0 && l == 1 && m == 2) continue; // GAC if (k == 2 && l == 0 && m == 1) continue; // A*GC if (j == 0 && l == 2 && m == 1) continue; // AG*C if (j == 0 && k == 2 && m == 1) continue; dp[i + 1][k][l][m] += dp[i][j][k][l]; } } } } } // 答えを集計 mint ans = 0; REP (j, 4) { REP (k, 4) { REP (l, 4) { ans += dp[N][j][k][l]; } } } // 出力 cout << ans << endl; }
