前回のコンテスト，ABC122の復習メモを残しておく．

問題

問題文

整数 $N$ が与えられます。次の条件を満たす長さ $N$ の文字列の数を $10^9$ で割った余りを求めてください。

• A, C, G, T 以外の文字を含まない。
• AGC を部分文字列として含まない。
• 隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

制約

• $3\leq N\leq100$

解法（考え方）

単純な全探索の計算量は $O(4^N)$ ．しかし「隣り合う文字列を入れ替えた時に”AGC”を含んではいけない」という制約は，新しくi番目の文字を決定するには直前の3文字のみが関与することがわかる．

ダメなケースというのは例えば

• 3文字: “AGC”, “GAC”, “ACG”

• 4文字: “A?GC”, “AG?C”

であるが，コツとして，文字列が制約を守っているかどうかを↑のように自分でパターンを書き出しすのではなく，プログラムしてあげるほうが良いということ（公式の解答でやられている）．こういう感じ．

{{< gist raahii 1f5d88bda3ec4b09e26aeb55b48f3ca8 >}}

これがまた，Goだと string は要素の入れ替えができなくて辛い感じになるのですが笑（まぁ全角文字が入ったりするとstringの要素はきちんと1文字に対応しないので，できない方が良いとも言える？）．

あとはオーバーフローするので余りを取ることを忘れないようにすること．dpテーブルの構築時，最後の和を取る部分の両方で使う．

DPによる解法

解法の方向性がわかったところで，DPで解く方法を考える．この場合，i番目に文字jを採用できる場合の数をテーブルに埋めていく．

制約の全くない単純な数え上げをするケースをまず考えると，遷移式は

$dp[i+1][j] = \sum_{k} dp[i][k]$

のように書くことができ，コードは次のようになる．

{{< gist raahii 3a69a715536f5e451e9bc3c491632590 >}}

この基本形を意識しながら，直前の3文字の状態を保持するためにテーブルを dp[i][j][k][l] のように拡張する．添字はそれぞれ直近3番目(j)，直近2番目(k)，直近1番目(l)を示す．そうすると遷移式は次のようにかける．

ここで，j k l m の4つの文字を並べたときに，先のokに渡してtrueとなるもののみを遷移可能として足せば良い．dpを使うことで計算量は $O(N)$ になる．for文が多くて結構つらいが完成してみると難しいところは特にない．初期値をどうするかは割と迷った．

{{< gist raahii 019732bf3d8bccd5a0a8f2764a5d4169 >}}

メモ化による解法

これは模範解答のpdfと同じなので改めて説明する必要もないけれど，自分で理解する用で書いてみた．メモ化の方が再帰を使うのですっきり書ける．

{{< gist raahii ea62641e1f2ba6d9cbfa6aac777914e8 >}}

感想

この手の問題は経験値な気がする．解けるようになるのは楽しいけど，きちんと各解法を理解して，何故これで高速化できるのか，どれくらい高速化されるのかを説明できなければ，実務ではかすりもしない気がする．精進．