ABC122 D - We Like AGC (400)
すごく強引に解きました。
解説のDFSのがスマート。
$ dp[i][j][k][l][m]
をi文字番目で3文字前がj、2文字前がk、1文字前がl、今の文字がmの場合の場合とする。
"AGCX", "ACGX", "GACX", "XAGC", "XACG", "XGAC", "AGXC", "AXGC"の場合は条件を満たさないので上記は0
これを愚直に実装
$ O(N \times 4^5)
なので
$ O(N)
https://atcoder.jp/contests/abc122/tasks/abc122_d
https://atcoder.jp/contests/abc122/submissions/4742910
#AtCoder
#ABC
#ABC122
#D
#400pt
#DP
#DFS