ABC 122 D We like AGC

Abstract

• ABC 122 D問題(400点) 「We like AGC」 を解きました。
• python

こんな人にオススメ

• 数え上げの練習がしたい
• dpの練習

problem

• 以下の条件を満たす文字列を AGC文字列 とする。
  1. A,G,C,T　の４文字でできている
  2. "AGC"という文字列を含まない
  3. 任意の文字において、隣の文字と入れ替える操作をしても、"AGC"という部分文字列を作れない
• 整数N(>=3)が与えられた時に、長さNの AGC文字列 が何通りあるかもとめよ。(10**9+7でMODをとる)

atcoder.jp

constraints

• 3<=N<=100

input

• N

output

• 長さNの AGC文字列 の数

Idea

• 長さNの文字列を全通り作って試すと、4**N個の文字列ができる。これは、多すぎてN=100の時に大変なことになる。
• 文字列が違反するかどうかは、途中に特定のパターンを含むかどうかで、判定できる。(GAC,ACG,A?GC,AG?C)

solution

• 長さ iの AGC文字列 は何通りできるかを、i=3からi=Nまで計算していく
• 動的計画法

point

• 一文字増やす際に、違反させないように増やす。
  • チェックに必要な4文字以外の情報はいらない。

    1. dpの配列は、今の状態と、次の状態さえ持てればいい(N次元もいらない)
    2. 前の３文字の情報は、dpを辞書型にすることで、前３文字をkeyとして、数値にアクセスする。
    

• 正規表現を使って、違反のパターンを シンプルに記述
• MODするのを忘れない。

solution

import re
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N = int(input())
CHAR = ["A", "C", "G", "T"]
invalid_pattern = r'ACG|GAC|A.?GC|AG.?C'
invalid_reg = re.compile(invalid_pattern)

# 一個前の状態だけあればいいので、一次元のdpでいい
dp = {a+b+c: 1 if not invalid_reg.search(a+b+c)
      else 0 for a in CHAR for b in CHAR for c in CHAR}


# dpで、最後の３文字を記憶-> 新しく加える文字4通りで、加えても大丈夫なら遷移。
# loop iでは、i+4文字の長さの条件を満たす文字列の数を数える
for i in range(N-3):
    next_dp = {key: 0 for key, _ in dp.items()}
    for key, val in dp.items():
        for c in CHAR:
            next_val = key+c
            if invalid_reg.search(next_val):
                # 新しい文字を追加した時に、条件に違反するなら遷移なし
                continue
            else:
                # 加えても大丈夫なので遷移
                next_dp[(key+c)[1:]] += dp[key]
    dp = next_dp
    for key in dp.keys():
        dp[key] %= MOD
# sumの後のMODを忘れない
print(sum(dp.values()) % MOD)

最後に

• 解説pdfでは、メモ化佐伯の解法が書いてあって、そっちでもできる。
• 数え上げのDP苦手なので、難易度400点以上に思えたけど、しっかり練習していきたい。