[AtCoder] ABC 122 D – We Like AGC

2019年5月24日

問題

方針

どのような文字列を除くか

どのような部分文字列を取り除くかを考えます。

長さが \( 3 \) の文字列では、"AGC", “ACG", “GAC" が取り除かれる文字列になります。この文字列を含む文字列は正しくありません。次に、長さが \( 4 \) の文字列では、任意の文字を “X" として、"AGXC", “AXGC" となります。長さ \( 5 \) の文字列で部分文字列としてのパターンは存在しません。

動的計画法

\( A = 0, G = 1, C = 2, T = 3 \) とします。

新たに文字の長さを増やすときに注意することは、後ろの三文字を見るだけで良いので、配列 \( dp[i][j][k][l]\) を \( i \) 文字目まで見た時、後ろの文字列が \( j, k, l\) となるときのパターン数とします。

ここで、変数 \( m \ (0 \leq m \leq 3)\) を用いて動的計画法の遷移を次のように表します。

\[ dp[i][j][k][l] = dp[i][j][k][l]  + dp[i – 1][k][l][m]\]

取り除かれる添え字は、\(( i = A, j = G, k = C) \), \( (i = A, j = C, k = G\)), \( (i = G, j = A, k = C)\), \( (j = A, k = 1, m = 2) \), \( (j = 0, l = G, m = 2)\) となります。

コード

提出したコード

感想

あまり理解できていないです。類題を解く必要がありそうです。