AtCoder Beginner Contest 122 Dを漸化式で解く

A-Cの3完．Dは解けず．64個書き出せば解ける，とは思ったのだがそこから手が進まず．動的計画法を使いこなせていない．

以下は解説を見てから．最後3桁についての場合の数で漸化式． 邪道かもしれないけど，正規表現を使うと場合分けが減って楽．

import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
    memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))

そして，このABCとは関係ないけどAtCoderはnumpyが使えるらしいということを知ったのも今日の収穫．

to/do ・DP全般 ・DFS、BFS、グラフDFS、グラフBFS ・union-find ・ヒープ，スタックなど ・グラフ，二分木など ・ダイクストラ法、ベルマンフォード法