第5回 ドワンゴからの挑戦状 予選 C - k-DMC

内容

• 第5回 ドワンゴからの挑戦状 予選 C - k-DMCをpythonで解いた。

  問題

• atcoder.jp

考えたこと

• クエリの数が少ないので、各クエリにO(N)くらいで答えればいいや。
• 区間の幅を固定して、スライドさせていくと解けそう。
  • 尺取りだ!

    ポイント

• 区間の中の、Dの数、Mの数、DMのくみの数を記録しておく。

  実装

N = int(input())
S = input()
Q=int(input())
Queries=list(map(int,input().split()))

for wid in Queries:
    ans=0

    d_cnt=0#[i,i+wid)に含まれる Dの数
    m_cnt=0#[i,i+wid)に含まれる Mの数
    dm_cnt=0#[i,i+wid)に含まれる [D,M]の組み合わせ数

    for i in range(wid):
        if S[i]=="D":
            d_cnt+=1
        elif S[i]=="M":
            m_cnt+=1
            dm_cnt+=d_cnt
        elif S[i]=="C":
            ans+=dm_cnt


    #尺取り
    for i in range(N-wid):
        remove=S[i]
        #removeする要素に応じて、各cntの値を更新する
        if remove=="D":
            d_cnt-=1
            #左端のDがなくなると、m_cntだけDMの組み合わせ数が減る
            dm_cnt-=m_cnt
        elif remove=="M":
            #左端のMがなくなっても、DMのくみの数は変わらない。(左端のMはDとペアを作れてないから)
            m_cnt-=1
        elif remove=="C":
            pass

        #addする要素に応じて、値を更新する
        new_add=S[i+wid]
        if new_add=="D":
            d_cnt+=1
        elif new_add=="M":
            #区間の右端のMが増えると、区間内のDの数だけ、DMの組み合わせが増える
            m_cnt+=1
            dm_cnt+=d_cnt
        elif new_add=="C":
            #左端にCが入ってくると、DMの組の数だけ、DMCができる
            ans+=dm_cnt

    print(ans)

終わりに