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

問題

問題文

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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