ABC122 D - We Like AGC - ツバサの備忘録

解法

4次元DPをします。
問題の条件を満たす文字列 $s$ が存在したときに、新しく最後尾に1文字加えてなお問題の条件を満たすのがどういう場合かを考えています。

追加する文字が'A'または'T'のとき
$s$ がどうなっていても問題の条件を満たします。
追加する文字が'G'のとき
$s$ の後ろ2文字について見たときに、"AC"となっている場合、文字を追加してしまうと"ACG"となり、これは'C'と'G'を置換することで問題の条件を満たさなくなります。
追加する文字が'C'のとき
$s$ の後ろ2文字についてみたときに、"AG"もしくは"GA"となっている場合、'C'は追加できません。
加えて、"AXG"もしくは"AGX"であった場合にも追加することはできません(Xは任意の文字列です)。

以上より、新しく文字を追加するために見るべき部分は、多くて後ろの3文字であり、それより前の文字は見る必要がありません。
'A'=0,'T'=1,'G'=2,'C'=3として、以下のようなDPを考えます。

$dp[i][j][k][l] =$ 長さ $i$ で、後ろの3文字が $lkj$ と並ぶような文字列の場合の数

$dp[i+1][j][k][l]$ を求める方法を考えてみます。
完成する文字列の後ろ4文字が $mlkj$ となっているとします。
基本的な、特に条件がない場合の遷移は
$\displaystyle dp[i+1][j][k] = \sum_{m=0}^{3} dp[i][k][l][m]$
となります。が、いくつか除外しなければならないパターンが存在するので、 $j$ で場合分けをしていきます。

$j=0,1$ のとき
これは一番後ろに'A'もしくは'T'を追加する場合だったので、 $l,k,j$ に制約はありません。よって、全部上記の遷移をして問題ありません。
$j=2$ のとき
これは'G'を追加するパターンなので、完成後の3文字が"ACG"になってはいけません。これは、 $l=0,k=3$ のときなので、
$dp[i+1][2][3][0] = 0$
となります。
それ以外のパターンは、最初に述べた遷移で問題ないです。
$j=3$ のとき
'C'を追加するパターンです。 $j=2$ と同様、 $(l,k) = (0,2) , (2,0)$ の場合は
$dp[i+1][3][k][l] = 0$
となります。
また、 $(l,k) \neq (2,0),(0,2)$ かつ、 $k=2$ もしくは $l=2$ が成り立つ場合は、"AXGC"、"AGXC"のパターンを排除しなければならないため、
$\displaystyle dp[i+1][3][k] = \sum_{m=1}^{3} dp[i][k][l][m]$
という遷移をします。
そのほかのパターンは、最初の遷移を適用できます。

あとは、この遷移を行っていくことで、
$dp[n][j][k][l]$ の総和が答えとなります。
初期値は $dp[0][1][1][1] = 1$ です。'T'は、問題の条件と唯一無縁の文字なので、この文字が無限に並んでいるイメージを持っておけばよいです。

感想

このコンテストではDから解いたのですが、全く解けなくて結局先にABCの問題へ移行しました。
原因は包除原理だと決め込んでいたせいでした。パッと見たときに、問題の条件を満たさないものを全体から引けば楽そう！と思ってしまいました…ここら辺の区別をしっかりしたいですね。
包除について考えていた際にはすでにDPをするものと思っていたので、長さ $X$ の文字列が数え終わったと仮定した場合に、 $X+1$ の文字列の種類を数えるにはどうすればいいか？という部分から考えていき、上のような解法を考えました。
実装面では、ほぼバグを埋め込まなかったorすぐに見つかったので、良かったかなと思います。

解法

感想