ABC122 D - We Like AGC (400)

D - We Like AGC

概要

長さNの文字列で、下記の条件をすべて満たすものはいくつあるか。

• アルファベットA, G, C, Tからなる
• "AGC"という文字列を含まない
• 隣接する2文字を交換しても"AGC"を含むようにできない

(mod 10^9+7して解答)

制約

3 ≦ N ≦ 100

方針

DP。
もしNGパターンがない場合、次のようにDPを構成することが出来る。
dp[i][j]：長さiの文字列でi番目がj(0:A, 1:G, 2:C, 3:T)であるものの総数
dp[i][j] += dp[i-1][m] (m = 0, 1, 2, 3)

次にNGパターンを考える。
3文字でNGなパターン：AGC, ACG, GAC
4文字でNGなパターン：A*GC, AG*C
よって最後の3文字を記憶し、NGパターンには遷移しないようなDPを考えればよい。

dp[i][j][k][l]：長さiの文字列でi-2番目がj、i-1番目がk、i番目がlであるものの総数
DPを遷移させる式は次の通り
dp[i][j][k][l] += dp[i-1][m][j][k] (m = 0, 1, 2, 3)

ただし、このときNGパターンへ遷移しないようにする。
例えば
dp[i][G][A][C] += dp[i-1][m][G][A]
や
dp[i][G][k][C] += dp[i-1][A][G][k]
はNGパターンへの遷移なので、このような足し算は行わない。

感想

下記を参考にしました。
betrue12.hateblo.jp

また変数をA = 0, G= 1, C = 2, T = 3と置くと見やすいです。
これは下記提出を参考にしました。
Submission #4700943 - AtCoder Beginner Contest 122

解答

Submission #4702533 - AtCoder Beginner Contest 122

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int A = 0, G = 1, C = 2, T = 3;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	ll MOD = 1e9+7;
 
	ll dp[N+1][4][4][4];
	rep(i, N+1) rep(j, 4) rep(k, 4) rep(l, 4) dp[i][j][k][l] = 0;
 
	rep(j, 4) rep(k, 4) rep(l, 4){
		if(j == A && k == G && l == C) continue;
		if(j == A && k == C && l == G) continue;
		if(j == G && k == A && l == C) continue;
		dp[3][j][k][l] = 1;
	}
 
	for(int i = 4; i <= N; i++){
		rep(j, 4){
			rep(k, 4){
				rep(l, 4){
					rep(m, 4){
						if(j == A && k == G && l == C) continue;
						if(j == A && k == C && l == G) continue;
						if(j == G && k == A && l == C) continue;
						if(m == A && k == G && l == C) continue;
						if(m == A && j == G && l == C) continue;
						dp[i][j][k][l] += dp[i-1][m][j][k];
						dp[i][j][k][l] %= MOD;
					}
				}
			}
		}
	}
 
	ll ans = 0;
	rep(j, 4){
		rep(k, 4){
			rep(l, 4){
				ans += dp[N][j][k][l];
				ans %= MOD;
			}
		}
	}
 
	cout << ans << endl;
}