AtCoder Beginner Contest 122：D - We Like AGC
問題
解法
dp(i, j, k, l) := 今 i - 1 文字目まで考えて，i - 3 文字目が j，i - 2 文字目が k, i - 1 文字目が l のときの，i 文字目から先の通り数
と DP を定義する．次の１文字（すなわち i 文字目）を決めるとき 'A', 'T', 'G', 'C' の４通りある．次におく文字を c とおくと (j + k + l + c) という長さ４の文字列が出来る．この中で任意の隣り合う要素をスワップして "AGC" という部分文字列が現れるか愚直に確かめればよい．DP の定義で決めた文字列のうち直前の３文字を持っておくのはこの判定を行うため．逆に，今まで決めた文字列全てを持っておく必要はない．なぜならば，新しく加えた文字とスワップ出来るのは i - 1 文字目とだけであり， i - 1 文字目が変わったことで "AGC" という文字列が出来る可能性があるのは i - 3 文字目までであるから．計算量を特に気にしなくて実装して O(N * 4^4 * 3^2)．
解答
