ABC122 D - We Like AGC

atcoder.jp

ABC122は出れなかったけど、出てても解けなかった。解説見てもすぐには理解出来なかったし。。 DPというのはまぁそうだろうなという感じだけど、その後の考察がだめだ。今後はDPな気がするけどうまく考えられない時にはメモ化再帰で解くことも検討してみる。

この記事ではメモ化再帰でやってみようと思った時の流れをシミュレートしてみる。

1. とりあえず再帰で全パターン網羅するやつを書いてみる

def dfs(cur, s):
    if cur==n:
        if re.search(r"(AGC|ACG|GAC|AG.C|A.GC)", s):
            return 0
        else:
            return 1
    res = 0
    for c in "AGCT":
        res = (res + dfs(cur+1, s+c))%MOD

    return res

2. 直前4文字だけ見ればいいことに気付く

気付けるかは分からないが、、 4文字見た時点で判定ができるので、最後に正誤を判定するのではなく枝刈りするような形にしている。 回答見る前にAGC以外のパターンとしてACGやGACがあることは分かっていたが、A*GCやAG*Cもだというのは気付いてなかったのでそこもハマりそう

def dfs(cur, s):
    if cur==n:
        return 1
    res = 0
    for c in "AGCT":
        if not re.search(r"(AGC|ACG|GAC|AG.C|A.GC)", s+c):
            res = (res + dfs(cur+1, s[1:]+c))%MOD

    return res

3. メモ化

ここまでくればcurとsでメモしていけばいいことは分かりやすい