Problem:


Score : 600 points

Problem Statement

In Dwango Co., Ltd., there is a content distribution system named 'Dwango Media Cluster', and it is called 'DMC' for short.

The name 'DMC' sounds cool for Niwango-kun, so he starts to define DMC-ness of a string.

Given a string S of length N and an integer k (k \geq 3),
he defines the k-DMC number of S as the number of triples (a, b, c) of integers that satisfy the following conditions:

0 \leq a < b < c \leq N - 1

S[a] = D

S[b] = M

S[c] = C

c-a < k

Here S[a] is the a-th character of the string S. Indexing is zero-based, that is, 0 \leq a \leq N - 1 holds.

For a string S and Q integers k_0, k_1, ..., k_{Q-1}, calculate the k_i-DMC number of S for each i (0 \leq i \leq Q-1).

Constraints

3 \leq N \leq 10^6

S consists of uppercase English letters

1 \leq Q \leq 75

3 \leq k_i \leq N

All numbers given in input are integers

Input

Input is given from Standard Input in the following format:

N
S
Q
k_{0} k_{1} ... k_{Q-1}

Output

Print Q lines.
The i-th line should contain the k_i-DMC number of the string S.

Sample Input 1

18
DWANGOMEDIACLUSTER
1
18

Sample Output 1

1

(a,b,c) = (0, 6, 11) satisfies the conditions.

Strangely, Dwango Media Cluster does not have so much DMC-ness by his definition.

Sample Input 2

18
DDDDDDMMMMMCCCCCCC
1
18

Sample Output 2

210

The number of triples can be calculated as 6\times 5\times 7.

Sample Input 3

54
DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED
3
20 30 40

Sample Output 3

0
1
2

(a, b, c) = (0, 23, 36), (8, 23, 36) satisfy the conditions except the last one, namely, c-a < k_i.

By the way, DWANGO is an acronym for "Dial-up Wide Area Network Gaming Operation".

Sample Output 4

30
DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC
4
5 10 15 20

Sample Output 4

10
52
110
140



Sample input:
18
DWANGOMEDIACLUSTER
1
18


Sample output:
1

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

def solve(N, S_arr, k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM
    for i in range(k, N):
        if S_arr[i-k] == 1:
            D -= 1
            DM -= M
        elif S_arr[i-k] == 2:
            M -= 1

        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM

    return ans

def main():
    N = int(input())
    S = input()
    Q = int(input())
    ks = list(map(int, input().split()))

    def func(ch):
        if ch == 'D':
            return 1
        if ch == 'M':
            return 2
        if ch == 'C':
            return 3
        return 0
        
    S_arr = np.array([func(ch) for ch in S], dtype = np.int32)
    for k in ks:
        print(solve(N, S_arr, k))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', "i8(i8, i4[:], i8)")(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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

def func(ch):
    if ch == 'D':
        return 1
    if ch == 'M':
        return 2
    if ch == 'C':
        return 3
    return 0
    
S_arr = np.array([func(ch) for ch in S], dtype = np.int32)

@njit("i8(i8, i4[:], i8)", cache = True)
def solve(N, S_arr, k):
    ans = 0
    D = 0
    M = 0
    DM = 0
    for i in range(k):
        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM
    for i in range(k, N):
        if S_arr[i-k] == 1:
            D -= 1
            DM -= M
        elif S_arr[i-k] == 2:
            M -= 1

        if S_arr[i] == 1:
            D += 1
        elif S_arr[i] == 2:
            DM += D
            M += 1
        elif S_arr[i] == 3:
            ans += DM

    return ans

for k in ks:
    print(solve(N, S_arr, k))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
q = int(input())
ks = list(map(int, input().split()))
ans = [None]*q
# DMC
for ind,k in enumerate(ks):
    ms = 1 if s[0]=="M" else 0
    cs = 1 if s[0]=="C" else 0
    mcs = 0
    j = 0
    val = 0
    for i in range(n):
        if s[i]!="D":
            if s[i]=="M":
                ms -= 1
                mcs -= cs
            elif s[i]=="C":
                cs -= 1
            continue
        if j<i:
            j = i
            ms = 0
            cs = 0
            mcs = 0
        while j+1<n and j+1-i<k:
            j += 1
            if s[j]=="M":
                ms += 1
            elif s[j]=="C":
                cs += 1
                mcs += ms
        val += mcs
#         print(i,ms,cs)
    ans[ind] = val
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
q=int(input())
query=list(map(int,input().split()))
for k in query:
  ds=0
  ms=0
  dms=0
  ans=0
  for i in range(n):
    if s[i]=='D':
      ds+=1
    elif s[i]=='M':
      ms+=1
      dms+=ds
    elif s[i]=='C':
      ans+=dms
    if i>=k-1:
      if s[i-k+1]=='D':
        dms-=ms
        ds-=1
      elif s[i-k+1]=='M':
        ms-=1
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n = int(input())
S = input().rstrip()
q = int(input())
K = tuple(map(int, input().split()))
L = [0]*q
M = [0]*n
C = [0]*n
cnt_M = [0]*n
cnt = 0
for i in range(n-1, -1, -1):
  s = S[i]
  if s == "M":
    M[i] = cnt
    cnt_M[i] = 1
  elif s == "C":
    C[i] = 1
    cnt += 1
M = tuple(accumulate(M))
C = list(accumulate(C[::-1]))[::-1]
cnt_M = tuple(accumulate(cnt_M))
for i, s in enumerate(S):
  if s == "D":
    for j, k in enumerate(K):
      temp = M[min(i+k-1, n-1)] - M[i]
      if i+k < n:
        temp -= C[i+k] * (cnt_M[i+k-1]-cnt_M[i])
      L[j] += temp
print(*L, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())
K = list(map(int,input().split()))

for ii in range(q):
    # D = [[0] * 3 for i in range(n)]
    d = 0
    m = 0
    dm = 0
    ans = 0
    k = K[ii]
    for i in range(n):
        # for j in range(3):
        #     D[i][j] = D[i-1][j]
        
        if i-k >= 0:
            if s[i-k] == "D":
                d -= 1
                dm -= m
            if s[i-k] == "M":
                m -= 1
        
        if s[i] == "D":
            d += 1
        if s[i] == "M":
            m += 1
            dm += d
        if s[i] == "C":
            ans += dm
    print(ans)
    # print(D)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a += m
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a += m
        if S[i-1]=='M':
            m -= 1
            a -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            b += a
            if i==e:
                break
    ans.append(b)
printrows(ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0

n=int(input())
s=[ord(i) for i in input()]
q=int(input())
kin=[int(i) for i in input().split()]

D,M,C=[ord(i) for i in 'DMC']

for i in range(q):
    k=kin[i]
    nd=nm=ndm=ans=0
    st=deque()
 
    for j in range(n):
        ch=s[j]
        if ch==C:
            ans+=ndm
        if j<k-1:
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
        else:
            pre=s[j-k+1]
            if pre==D:
                nd-=1
                ndm-=nm
            elif pre==M:
                nm-=1
            if ch==M:
                ndm+=nd
                nm+=1
            elif ch==D:
                nd+=1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    q = deque([])
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
            q.append(d)
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1
                
        
    return ans
for i in k:
    print(search(i))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    s=input()
    Q=int(input())
    A = tuple(map(int, input().split()))
    for k in A:
        dmc=0
        d=0
        m=0
        c=0
        dm=0
        mc=0
        
        for i in range(k):
            if s[i]=="D":
                d+=1
            elif s[i]=="C":
                c+=1
                mc+=m
                dmc+=dm
            
            elif s[i]=="M":
                m+=1
                dm+=d

        for i in range(1,N-k+1):
            if s[i-1]=="D":
                dm-=m
                d-=1
            elif s[i-1]=="M":
                mc-=c
                m-=1
            elif s[i-1]=="C":
                c-=1
            se=s[i+k-1]
            if se=="D":
                d+=1
            elif se=="C":
                c+=1
                mc+=m
                dmc+=dm
            
            elif se=="M":
                m+=1
                dm+=d

        print(dmc)

            




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
q = inn()
kl = inl()
accd = [0]*(n+1)
accm = [0]*(n+1)
for i in range(n):
    accd[i] = accd[i-1] + (1 if s[i]=='D' else 0)
    accm[i] = accm[i-1] + (1 if s[i]=='M' else 0)
#ddprint(accd)
#ddprint(accm)
for k in kl:
    #ddprint(k)
    dm = 0
    dmc = 0
    for i in range(1,n):
        if i>=k and s[i-k]=='D':
            dm -= accm[i-1]-accm[i-k]
        if s[i]=='M':
            dm += accd[i-1]-accd[max(-1,i-k)]
        if s[i]=='C':
            dmc += dm
        #ddprint(f"{i=} {dm=} {dmc=}")
    print(dmc)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = input()
    q = int(input())
    K = list(map(int,input().split()))
    # print(s)

    for i in range(q):
        ans = 0
        d = 0
        m = 0
        dm = 0
        k = K[i]
        for j in range(n):

            if j-k >= 0:
                if s[j-k] == "D":
                    d -= 1
                    dm -= m
                elif s[j-k] == "M":
                    m -= 1

            if s[j] == "D":
                d += 1
            elif s[j] == "M":
                m += 1
                dm += d
            elif s[j] == "C":
                ans += dm
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    S=input()
    Q=I()
    K=LI()
    ans=0
    
    
    
    for k in K:
        d=0
        m=0
        temp=0
        ans=0
        for i in range(k):
            if S[i]=="D":
                d+=1
            elif S[i]=="M":
                m+=1
                temp+=d
            elif S[i]=="C":
                ans+=temp
                #print(0,i,d,m)
        
        for i in range(k,N):
            if S[i-k]=="D":
                d-=1
                temp-=m
            elif S[i-k]=="M":
                m-=1
            
            if S[i]=="D":
                d+=1
            elif S[i]=="M":
                m+=1
                temp+=d
            elif S[i]=="C":
                ans+=temp
                #print(1,i,d,m)
                
        print(ans)
            
                
                
            
            
            

main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N = int(input())
    S = input()
    Q = int(input())
    *k, = map(int, input().split())

    acd = [0]*(N+1)
    acm = [0]*(N+1)
    acc = [0]*(N+1)
    acmc = [0]*(N+2)

    for i in range(1, N+1):
        acd[i] = acd[i-1] + (S[i-1]=="D")
        acm[i] = acm[i-1] + (S[i-1]=="M")
        acc[i] = acc[i-1] + (S[i-1]=="C")

    ans = 0
    for i in range(1, N+1):
        if S[i-1]=="M":
            ans += acd[i-1]*(acc[N]-acc[i])

    for i in range(1, N)[::-1]:
        acmc[i] += acmc[i+1]
        if S[i-1]=="M":
            acmc[i] += acc[N]-acc[i]

    for i in k:
        v = 0
        for j in range(1, N+1):
            if S[j-1]=="D":
                v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
        print(ans-v)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Q = int(input())
*k, = map(int, input().split())

acd = [0]*(N+1)
acm = [0]*(N+1)
acc = [0]*(N+1)
acmc = [0]*(N+2)

for i in range(1, N+1):
    acd[i] = acd[i-1] + (S[i-1]=="D")
    acm[i] = acm[i-1] + (S[i-1]=="M")
    acc[i] = acc[i-1] + (S[i-1]=="C")

ans = 0
for i in range(1, N+1):
    if S[i-1]=="M":
        ans += acd[i-1]*(acc[N]-acc[i])

for i in range(1, N)[::-1]:
    acmc[i] += acmc[i+1]
    if S[i-1]=="M":
        acmc[i] += acc[N]-acc[i]

for i in k:
    v = 0
    for j in range(1, N+1):
        if S[j-1]=="D":
            v += (acm[min(N, i+j-1)]-acm[j]) * (acc[N]-acc[min(N, i+j-1)]) + acmc[min(i+j, N)]
    print(ans-v)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
q = int(input())
query = list(map(int,input().split()))
for k in query:
  ans = 0
  dp0,dp1,dp2 = 0,0,0
  for i in range(n):
    if s[i] == "D":
      dp0 += 1
    elif s[i] == "M":
      dp1 += 1
      dp2 += dp0
    elif s[i] == "C":
      ans += dp2
    if i >= k-1:
      if s[i-k+1] == "D":
        dp0 -= 1
        dp2 -= dp1
      elif s[i-k+1] == "M":
        dp1 -= 1
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
  n = int(input())
  S = input()[:-1]
  q = int(input())
  K = map(int, input().split())
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))
 
for k in K:
    res = 0
    d = 0
    m = 0
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            dm += d
            m += 1
        elif S[i] == 'C':
            res += dm
        if i + 1 - k >= 0:
            if S[i + 1 - k] == 'D':
                d -= 1
                dm -= m
            elif S[i + 1 - k] == 'M':
                m -= 1
 
    print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

for k in K:
    res = 0
    d = 0
    m = 0
    dm = 0
    for i in range(N):
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            dm += d
            m += 1
        elif S[i] == 'C':
            res += dm
        if i + 1 - k >= 0:
            if S[i + 1 - k] == 'D':
                d -= 1
                dm -= m
            elif S[i + 1 - k] == 'M':
                m -= 1

    print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input().rstrip()
    Q = int(input())
    k = list(map(int, input().split()))

    for l in k:
        D = 0
        M = 0
        tmp = 0
        ans = 0
        for i in range(N):
            if i >= l:
                if S[i-l] == 'D':
                    tmp -= M
                    D -= 1
                if S[i-l] == 'M':
                    M -= 1
            if S[i] == 'D':
                D += 1
            if S[i] == 'M':
                M += 1
                tmp += D
            if S[i] == 'C':
                ans += tmp
        print(ans)

main()

Submission status: Accepted

Solution code:
N,S,Q,*k = open(0).read().split()
N,Q = map(int, (N,Q))
K = map(int, k)
for k in K:
  D = 0
  M = 0
  DM = 0
  DMC = 0
  for i in range(k):
    if S[i]=='D':
      D += 1
    elif S[i]=='M':
      DM += D
      M += 1
    elif S[i]=='C':
      DMC += DM
  for i in range(N-k):
    if S[i]=='D':
      DM -= M
      D -= 1
    elif S[i]=='M':
      M -= 1
    if S[i+k]=='D':
      D += 1
    elif S[i+k]=='M':
      DM += D
      M += 1
    elif S[i+k]=='C':
      DMC += DM
  print(DMC)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
# def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
s = S()
q = I()
def f(k):
    cnt = [0, 0, 0] # dの個数、mの個数、dmの個数
    ans = 0
    for i in range(n):
        if i - k >= 0:
            if s[i - k] == 'D':
                cnt[2] -= cnt[1]
                cnt[0] -= 1
            elif s[i - k] == 'M':
                cnt[1] -= 1
        if s[i] == 'D':
            cnt[0] += 1
        elif s[i] == 'M':
            cnt[1] += 1
            cnt[2] += cnt[0]
        elif s[i] == 'C':
            ans += cnt[2]
    return ans

K = LI()
for i in range(q):
    print(f(K[i]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
S = np.array(list(input()))
Q = int(input())
K = list(map(int, input().split()))


D_idx = S == 'D'
M_idx = S == 'M'
C_idx = S == 'C'

num_d = D_idx.cumsum(dtype=int)
num_m = M_idx.cumsum(dtype=int)

def count_DMC(k):
  _num_d = num_d.copy()
  _num_d[k:] = _num_d[k:] - _num_d[:-k] # k個先になったらカウントを減らす
  _num_m = num_m.copy()
  _num_m[k:] = _num_m[k:] - _num_m[:-k] # 同上
  num_dm = _num_d * M_idx # 'M'の位置における'DM'の個数
  num_dm[k:] -= D_idx[:-k] * _num_m[k-1:-1]
  return (num_dm.cumsum(dtype=int) * C_idx).sum()


for k in K:
  print(count_DMC(k))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    sl = input()
    q = int(input())
    kl = tuple(map(int,input().split()))

    for k in kl:
        # i文字目までのdとmとdmの数

        d = m = dm = ans = 0
        for i in range(n):
            if i - k >= 0:
                if sl[i-k] == "D":
                    d -= 1
                    dm -= m
                if sl[i-k] == "M":
                    m -= 1
            if sl[i] == "D":
                d += 1
            if sl[i] == "M":
                m += 1
                dm += d
            if sl[i] == "C":
                ans += dm

        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
K = list(map(int, input().split()))

ds = [0] * N
ms = [0] * N
dms = [0] * N
cpos = []
for i, c in enumerate(S):
    if i > 0:
        ds[i] += ds[i - 1]
        ms[i] += ms[i - 1]
        dms[i] += dms[i - 1]
    if c == "D":
        ds[i] += 1
    elif c == "M":
        ms[i] += 1
    elif c == "C" and i > 0 and dms[i - 1] > 0:
        cpos.append(i)

    if i > 0 and c == "M":
        dms[i] += ds[i - 1]

for k in K:
    ans = 0
    for i in cpos:
        ans += dms[i - 1]
        if i - k >= 0:
            ans -= dms[i - k] + (ms[i - 1] - ms[i - k]) * ds[i - k]
    print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    S=input()
    Q=int(input())
    *K,=map(int, input().split())

    for k in K:
        ans = 0
        d,m,dm=0,0,0
        j=0
        for i in range(N):
            if i-j == k:
                if S[j]=='D':
                    d -= 1
                    dm -= m
                elif S[j]=='M':
                    m -= 1
                j += 1

            if S[i] == 'D':
                d += 1
            elif S[i] == 'M':
                m += 1
                dm += d
            elif S[i] == 'C':
                ans += dm
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = input()
    q = I()
    K = LI()
    for k in K:
        fa = fb = ok = 0
        ans = 0
        for i in range(k):
            if s[i] == "D":
                fa += 1
            elif s[i] == "M":
                fb += 1
                ok += fa
            elif s[i] == "C":
                ans += ok
        for i in range(k,n):
            pi = s[i-k]
            if pi == "D":
                fa -= 1
                ok -= fb
            elif pi == "M":
                fb -= 1
            if s[i] == "D":
                fa += 1
            elif s[i] == "M":
                fb += 1
                ok += fa
            elif s[i] == "C":
                ans += ok
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
S = np.frombuffer(readline().rstrip(),'S1')
Q = int(readline())
query = map(int,read().split())

isD = S == b'D'
isM = S == b'M'
isC = S == b'C'

cumD = isD.cumsum(dtype=np.int64)
cumM = isM.cumsum(dtype=np.int64)

def F(K):
    """
    ・Cごとに数える。
    ・そのためには(i-K,i] 内のDMの個数を調べる（負インデックスには関係ない文字があると思っておく）
    ・区間内のDの個数、Mの個数が取得できれば、差分が取得できるので最後に累積和
    """
    # (i-K,i]内のDの個数、Mの個数
    D = cumD.copy(); D[K:] -= cumD[:-K]
    M = cumM.copy(); M[K:] -= cumM[:-K]
    # 最後がMのとき、Dの個数分増える
    DM = isM * D
    # 左端のDを捨てるとき、Mの個数分減る
    DM[K:] -= isD[:-K] * M[K-1:-1]
    np.cumsum(DM,out=DM)
    # Cごとに集計
    return DM[isC].sum()

print('\n'.join(str(F(K)) for K in query))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d = 0
        m = 0
        dm = 0
        dmc = 0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()