AtCoder ABC122 3完うーむ。

ABC122 序
- A
- B
- C
- D
  - 2019/03/30 やった
ABCはかったるい

ABC122 序

　どうせレートじわじわ落ちるんだろ？とおもいながら参加したら簡単でびびった。といいつつDはできず。(あとでさらえた)

A

　辞書。2分。

B

　ACGTが続く間旗立てたりおろしたりして長さを数えた。ここまで11分。ちなみに旗を上げ下げしなくてもできる。

C

　最初に'AC'のCの出て来る場所を例によって例のごとく旗を立てたりおろしたりして数え、あとは二分探索でいちいち区間がどこかみつけた。旗の上げ下げに失敗して1waのあと15分ほど無駄に消費した。

　二分探索するよりは最初から数えていって累積和的な長い配列をつくった方が速かったな。辞書への愛が足りない。

D

　AGC/ACG/GAC と ATGC / AGTC まではわかったがそこから先重複をどうやって省くのかについて横になって考えてたらいつのまにか終わっていた。こういうときDPをつかうと簡単にとけるらしい。なるほど。

2019/03/30 やった

　適当にやりだしたら微妙に答えがあわない。みなおしたがどこの考え方が間違っているのかよくわからず、結局他の人のコードをみたら、yydoco氏のものの核心が似てたので参考にしたら通ったのでなぜそこで通ったのか考えて説明を書いた↓。最初 GA[i] = G[i-1] - AG[i-1] としてたせいで微妙に合わなかった。何を消すべきかわかってないあたり、根本的によくわかっておらず辻褄合わせでなんとかしようとしていたことがわかる。考え方が正しくないのでいつまでやっても合わない。ひょっとして頭の中の基本ロジックが絵合わせなのかもしれんな。

def 解():
    N = int(input())
    iD = 10**9+7

    #3210
    #***A
    #***G
    #***C
    #***T
    #*ACG
    #*GAC
    #*AGC
    #AGGC #A*GC AG*C から重複を消したもの
    #AGTC
    #ATGC

    A = [0]*(N+1)
    G = [0]*(N+1)
    C = [0]*(N+1)
    T = [0]*(N+1)
    AC = [0]*(N+1)
    GA = [0]*(N+1)
    AG = [0]*(N+1)
    AGG = [0]*(N+1)
    AGT = [0]*(N+1)
    ATG = [0]*(N+1)

    A[1]=G[1]=C[1]=T[1]=1 #種
    for i in range(2,N+1):
        #前の桁の末尾に一文字足したものから条件を満たすものを消す
        A[i] = A[i-1] + G[i-1] + C[i-1] +T[i-1]
        A[i] %= iD
        G[i] = A[i] - AC[i-1]
        C[i] = A[i] - GA[i-1] - AG[i-1] - AGG[i-1] - AGT[i-1] - ATG[i-1]
        T[i] = A[i]

        #この桁の末尾の場合の数を計算
        AC[i] = A[i-1] - GA[i-1]  # **AC を計算するために**A*を使うが*GAC の分(*GA*)はこの桁で消えるので消す
        AG[i] = A[i-1]
        GA[i] = G[i-1]

        AGG[i]= AG[i-1]
        AGT[i]= AG[i-1]
        ATG[i]= A[i-2]

        G[i] %= iD
        C[i] %= iD
        AC[i] %= iD

    print((A[N]+G[N]+C[N]+T[N])%iD)
解()