We Like AGC [AtCoder Beginner Contest 122 D]

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

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc122/submissions/4712538

条件を満たす文字列を良い文字列と呼ぶことにする。
dp[s] := 最後の3文字がsである良い文字列の組合せ
最初はdp["###"]=1を初期値としておく。
#は何もないことにする。
dpの状態としては最後の3文字分だけ確保しておけば、文字を末尾に足したときに良い文字列でなくなるかどうかが判定できる。
自分はこういう特殊なやつはmapでdpを表現して、swapしながら、更新していくのが好きなので、それをやっている。
定数倍があまり問題にならない問題ではよくやる。
　
後ろ3文字sに文字cを末尾から足すことで良い文字列となるかをadd関数で判定している。
add(s,c) := 文字列sの末尾に文字cを足して、良い文字列ならs+cをした末尾3文字を、そうでないなら""を返す
これで""でなければ、これを次の状態として、次の状態のDPを作っていこう。

int N;
string S = "ACGT";
//---------------------------------------------------------------------------------------------------
bool contain(string s) {
	if (s.substr(0, 3) == "AGC") return true;
	if (s.substr(1, 3) == "AGC") return true;
	return false;
}
string add(string s, char c) {
	string res = s + c;
 
	if (contain(res)) return "";
 
	rep(i, 0, 3) {
		string tes = res;
		swap(tes[i], tes[i + 1]);
		if (contain(tes)) return "";
	}
 
	return res.substr(1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
 
	map<string, mint> dp;
	dp["###"] = 1;
 
	rep(i, 0, N) {
		map<string, mint> pd;
		fore(p, dp) {
			fore(c, S) {
				string nxt = add(p.first, c);
				if (nxt != "") pd[nxt] += p.second;
			}
		}
		swap(dp, pd);
	}
 
	mint ans = 0;
	fore(p, dp) ans += p.second;
	cout << ans << endl;
}