ABC122 We Like AGC

所感

最近残業が多くACできていなかったのでリハビリをね

問題概要

整数Nが与えられる。次の条件を満たす長さNの文字列の数を10⁹+7で割った余りを求めよ。
* A, C, G, T 以外の文字を含まない。
* "AGC" を部分文字列として含まない。
* 隣接する2文字の入れ替えを一回行うことで上記の条件に違反させることができない。

取った方針

長さN-1の条件を満たす文字列sに新たに1文字追記して長さNの文字列tを作ることを考える。
文字列sは条件を満たしているので、sの末尾2文字と追加した1文字からなる文字列が"AGC" "ACG" "GAC" のどれでもなければよい。(大嘘)
また、少し考えると末尾以外の追記は考えなくてよい気がしてくる。(条件を満たすある文字列uの末尾以外に追記して作られる文字列は条件を満たす文字列vの末尾に追記して得られる)(割と非自明だと思うけど信じる)
各長さについて、dp[n][k] := 長さnの文字列のうち、末尾がkであるものの数 とするDPで解が求まる。解はΣDP[N]。
しかし、二行目の仮定が大嘘なのでサンプルすら通らず死亡

正しい方針

条件を満たさない文字列には"取った方針"のものに加えてイカがある。
* "A?GC"
* "AG?C"
これを考慮して上記のDPを行うと正解が得られる。 ちゃんとフル参加してたら愚直との比較で上記ケースを見つけていたと思う(負け惜しみ)

得られた知見

• 既に条件を満たしているものからより大きな条件を満たすものを構成するDP

解くのに必要な要素

• DP

周辺調査によって得られた知見

特になし