ABC122 D - We Like AGC
解法
問題文の条件を満たすためには、具体的にどのような部分文字列が含まれていてはダメでしょうか。NGパターンを列挙してみましょう。
- 3文字のNGパターン
- もちろん
AGCはNGです。また、隣り合う2文字を入れ替えてAGCとなるGACとACGもNGです。3文字のNGパターンはこれで全部です。
- もちろん
- 4文字のNGパターン
Xを任意の文字としてAXGCはNGパターンです。最初の2文字を入れ替えるとAGCができてしまうからです。同様の理由でAGXCもNGです。4文字のNGパターンはこれで全部です。
列挙してみると意外と少ないことが分かります。また5文字以上のNGパターンはありません。「隣り合う2文字の入れ替えを高々1回行って、連続する3文字の並びを見る」という操作に関係する文字は、必ず連続する4文字以内に収まっているからです。
ということで、連続する4文字の並びを確認すればNGパターンかどうかが判定できることが分かりました。これを言い換えると
文字列の末尾に新しく1つ文字を足した時にNGパターンが新しく発生しないかどうかは、直近の3文字だけを見れば判定できる
ということになります。この考え方を元にDPを構成することが出来ます。
具体的には、
文字までの文字を決めていて、最近の3文字が左から
となっていて、NGパターンを含んでいない文字列の場合の数
という状態を持ってDPすることができます。 はそれぞれ文字
TAGC のどれかだと思ってください（後で実装について補足します）。
からの遷移を考えます。この文字列に文字
を足した時に新しく発生するNGパターンは、先ほど列挙した通り
- 3文字のNGパターン
- 文字列
が、
AGCGACACGのどれか
- 文字列
- 4文字のNGパターン
- 文字列
が、
Xを任意の文字としてAXGCAGXCのどちらか
- 文字列
です。これらNGパターンのどれにも当てはまらなければ、 に遷移することが出来ます。
このDPを全部計算して、最後に を全ての
について合計したものが答えとなります。
ACコード＆実装の補足
Submission #4700029 - AtCoder Beginner Contest 122
実装について少し補足します。まず先ほどの説明では文字をDPテーブルの添字として扱っていましたが、実装においては 0123 といった整数に対応させましょう。私のコードでは添字の 0123 が順に TAGC に対応しています。
次に初期状態について。DPの初期条件を考える時、初期状態（空文字列）には「直近の3文字」がないので少し困ります。今回の場合は「NGパターンに関して意味を持たないような文字」、つまり T が存在すると見なしてしまって良いです。先ほど T は添字 0 に対応させていたので、初期条件を dp[0][0][0][0] = 1 としています。
最後に関数 add(a, b) について。私のコードでは「変数 a に変数 b の値を足してMODを取る」という処理を add(a, b) にやらせています。a = (a+b) % MOD と同等の機能です。
