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 sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = input()
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            st = S[i]
            if st == "D":
                d += 1
            elif st == "M":
                m += 1
                dm += d
            elif st == "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.buffer.readline

def main():
    N = int(input())
    S = input()
    Q = input()
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            st = S[i]
            if st == "D":
                d += 1
            elif st == "M":
                m += 1
                dm += d
            elif st == "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
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = list(input())
Q = I()
k = LI()

cumD = [0]*N
cumM = [0]*N
cumDM = [0]*N

cumD[0] = 1 if S[0] == 'D' else 0
cumM[0] = 1 if S[0] == 'M' else 0

Clist = []
for i in range(1,N):
    cumD[i] = cumD[i-1]
    cumM[i] = cumM[i-1]
    cumDM[i] = cumDM[i-1]
    if S[i] == 'D':
        cumD[i] += 1
        continue
    if S[i] == 'M':
        cumM[i] += 1
        cumDM[i] += cumD[i-1]
        continue
    if S[i] == 'C':
        Clist.append(i)

for j in range(Q):
    ans = 0
    for i in Clist:
        if i-k[j] >= 0:
            ans += cumDM[i-1] - (cumD[i-k[j]])*(cumM[i-1]-cumM[i-k[j]]) - cumDM[i-k[j]]
        else:
            ans += cumDM[i-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = np.array(list('_' + sr()))
Q = ir()
K = lr()
isD = (S == 'D')
isM = (S == 'M')
isC = (S == 'C')
cumD = isD.cumsum()
cumM = isM.cumsum()

for k in K:
    x = cumD.copy()
    x[k:] -= cumD[:-k]
    x *= isM
    x[k+1:] -= isD[1:-k] * (cumM[k:-1] - cumM[:-k-1])
    answer = (x.cumsum() * isC).sum()
    print(answer)
# 05

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    Q = int(input())
    K = [int(k) for k in input().split()]
    for i, k in enumerate(K):
        Ans = 0
        NumD = 0
        NumM = 0
        NumDM = 0
        for i in range(N):
            if S[i] == "D": NumD += 1
            elif S[i] == "M": 
                NumM += 1
                NumDM += NumD
            if i >= k:
                if S[i - k] == "D":
                    NumD -= 1
                    NumDM -= NumM
                elif S[i - k] == "M": NumM -= 1
            if S[i] == "C": Ans += NumDM
        print(Ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def main():
    n=int(input())
    l=input()
    q=int(input())
    kl=tuple(map(int,input().split()))
    for k in kl:
        d=0
        m=0
        dm=0
        ans=0
        for j in range(n):
            if l[j]=='D':
                d+=1
            elif l[j]=='M':
                m+=1
                dm+=d
            elif l[j]=='C':
                ans+=dm
            if j>=k-1:
                if l[j-k+1]=='D':
                    dm-=m
                    d-=1
                elif l[j-k+1]=='M':
                    m-=1
        print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# 解説を見た
# よく理解していない

def main():
    n = int(input())
    s = input()
    q = int(input())
    *ks, = map(int, input().split())

    for k in ks:
        cnt = 0
        d, m, dm = 0, 0, 0
        for i in range(k):
            char = s[i]
            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        for i in range(k, n):
            p_char = s[i - k]
            char = s[i]
            if p_char == 'D':
                dm -= m
                d -= 1
            elif p_char == 'M':
                m -= 1

            if char == 'D':
                d += 1
            elif char == 'M':
                m += 1
                dm += d
            elif char == 'C':
                cnt += dm

        print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (N + 1)
ccounts = [0] * (N + 1)
for i in range(N):
  ccs[i + 1] = ccs[i] + cs[i] * (S[i] == "C")
  ccounts[i + 1] = ccounts[i] + (S[i] == "C")

#print(cs, c)
#print(ccs)
for k in qs:
  res = 0
  for i in d:
    l = i
    r = min(N, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (ccounts[r] - ccounts[l]))
  print(res)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = tuple(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Q = int(input())
K = list(map(int,input().split()))
DP = [[0,0,0]]
C = []
for i in range(N):
    q = DP[i][:]
    if S[i] == "D":
        q[0] += 1
    elif S[i] == "M":
        q[1] += 1
        q[2] += q[0]
    elif S[i] == "C":
        C.append(i+1)
    DP.append(q)

for k in K:
    ans = 0
    for c in C:
        if c < k:
            ans += DP[c][2]
        else:
            ans += DP[c][2] - DP[c-k][2] - DP[c-k][0]*(DP[c][1] - DP[c-k][1])
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
dd_append = dd.append
mm_append = mm.append
cc_append = cc.append
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            if i-q:
                ll = max(i-q, 0)
                As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
            else:
                As[j] += dm
    dd_append(d)
    mm_append(m)
    cc_append(dm)
for a in As:
    print(a)

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
qn = int(input())
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
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:
        ans = 0
        sa = 0
        sb = 0
        ns = 0
        for i in range(n):
            if i >= k:
                j = i-k
                if s[j] == "D":
                    sa -= 1
                    ns -= sb
                elif s[j] == "M":
                    sb -= 1
            if s[i] == "D":
                sa += 1
            elif s[i] == "M":
                sb += 1
                ns += sa
            elif s[i] == "C":
                ans += ns
        print(ans)
    return

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

Submission status: Accepted

Solution code:
N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
s=input()
q=int(input())
Q=map(int,input().split())
A=[-1]*(n+1)
C=[-1]*(n+1)
data=[0]*(n+1)
for i,si in enumerate(s):
    if si == "D":
        A[i]=count
    elif si == "M":
        count+=1
    elif si == "C":
        C[i]=count
# for i in range(len(data)-1):
#     data[i+1]+=data[i] 
for k in Q:
    count = ans = 0
    a_num=0
    for i in range(n):
        if A[i]!=-1:
            a_num+=1
            count+=A[i]
        if i-k>=0 and A[i-k]!=-1:
            a_num-=1
            count-=A[i-k]
        if C[i]!=-1:
            ans+=a_num*C[i]-count
    print(ans)
# print(A)
# print(C)
    
# print(data)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

# solve
# 解説AC
# いやなぜわからん
# 三段階に分けて個数を数えることができて,
# 1段階目D
# 2段階目DM
# 3段階目DMC
# とすれば考えやすい
# キョウプロ辞めたら？　
def solve():
    n = II()
    s = input().rstrip()
    q = II()
    k = LI()
    for ki in k:
        ans = 0
        d = 0
        dm = 0
        m =0
        for i in range(n):
            if i >= ki:
                if s[-ki +i] == "D":
                    d -= 1
                    dm -= m
                elif s[-ki + i] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            elif s[i] == "M":
                m += 1
                dm += d
            elif s[i] == "C":
                ans += dm
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

for ki in k :
    ret = 0
    dp = [0] * 3
    for i in range(N) :
        if i >= ki :
            j = i - ki
            if S[j] == 'D' :
                dp[0] -= 1
                dp[2] -= dp[1]
            elif S[j] == 'M' :
                dp[1] -= 1

        if S[i] == 'D' :
            dp[0] += 1
        elif S[i] == 'M' :
            dp[1] += 1
            dp[2] += dp[0]
        elif S[i] == 'C' :
            ret += dp[2]
            
    print(ret)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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:
        d = 0
        m = 0
        dm = 0
        ans = 0
        for i in range(n):
            if i >= k:
                j = i-k
                if s[j] == "D":
                    d -= 1
                    dm -= m
                elif s[j] == "M":
                    m -= 1
            if s[i] == "D":
                d += 1
            elif s[i] == "M":
                m += 1
                dm += d
            elif s[i] == "C":
                ans += dm
        print(ans)
    return


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

Submission status: Accepted

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

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

    for K in Ks:
        # [D, M, DM, DMC]
        dp = [0]*4
        for i in range(N):
            if i-K >= 0:
                sk = S[i-K]
                if sk == 'D':
                    dp[0] -= 1
                    dp[2] -= dp[1]
                elif sk == "M":
                    dp[1] -= 1
            s = S[i]
            if s == "D":
                dp[0] += 1
            elif s == 'M':
                dp[1] += 1
                dp[2] += dp[0]
            elif s == 'C':
                dp[3] += dp[2]
        
        print(dp[3])
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
D,M,C=map(ord,'DMC')
import numpy as np
S=np.array([ord(c) for c in input()])
input()
K=map(int,input().split())
iD=S==D
iM=S==M
iC=S==C
cD=np.cumsum(iD,dtype=np.int64)
cM=np.cumsum(iM,dtype=np.int64)
for k in K:
    cD2=cD-np.concatenate((np.zeros(k,dtype=np.int64),cD[:-k]))
    cM2=cM-np.concatenate((np.zeros(k,dtype=np.int64),cM[:-k]))
    DM=np.cumsum(cD2*iM-np.concatenate((np.zeros(k,dtype=np.int64),cM2[k-1:-1]*iD[:-k])))
    print(np.sum(iC*DM))

Submission status: Accepted

Solution code:
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+('M'==t)
  f='C'==t
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if'D'==t:a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Submission status: Accepted

Solution code:
e=enumerate
n,s,q,*k=open(0).read().split()
n=int(n)
m,c,x=eval('[0]*-~n,'*3)
for i,t in e(s,1):
  m[i]=m[i-1]+(t=='M')
  f=t=='C'
  c[i]=c[i-1]+f
  x[i]=x[i-1]+f*m[i]
for k in map(int,k):
  a=0
  for i,t in e(s):
    j=min(n,i+k)
    if t=='D':
      a+=x[j]-x[i]-(c[j]-c[i])*m[i]
  print(a)

Submission status: Accepted

Solution code:
from numpy import*
_,s,_,k=open(0)
s=array(list('='+s[:-1]))
d,m,c=[s==t for t in'DMC']
x,y=map(cumsum,(d,m))
for k in int32(k.split()):
  t=copy(x)
  t[k:]-=x[:-k]
  t*=m
  t[k+1:]-=d[1:-k]*(y[k:-1]-y[:~k])
  print(sum(cumsum(t)*c))

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.zeros(N+1,'U1')
S[1:] = list(readline().rstrip().decode('utf-8'))
Q = int(readline())
query = map(int,readline().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

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.empty(N+1,'S1')
S[1:] = np.frombuffer(readline(),dtype='S1')[:N]
Q = int(readline())
query = map(int,readline().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)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
import numpy as np
N = int(input())
S = np.array(list('-'+readline()),dtype='U1')
Q = int(input())
query = map(int,input().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
S = np.array(list('-'+input()),dtype='U1')
Q = int(input())
query = map(int,input().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
import numpy as np
I=input
N = int(I())
S = np.array(list('-'+I()),dtype='U1')
Q = int(I())
query = map(int,I().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
import numpy as np
I=input
N = int(I())
S = np.fromiter('-'+I(),dtype='U1')
Q = int(I())
query = map(int,I().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
S = np.fromiter('-'+input(),dtype='U1')
Q = int(input())
query = map(int,input().split())

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

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

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

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

from numpy import *

N = int(readline())
S = frombuffer(b'-'+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=int64)
cumM = isM.cumsum(dtype=int64)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

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(b'-'+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)

for K in query:
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    print((x.cumsum() * isC).sum())

Submission status: Accepted

Solution code:
from numpy import *
I=input
N=int(I())
S=array(list('-'+I()))
Q=int(I())
query = map(int,I().split())
D=S=='D';M=S=='M';C=S=='C'
d=D.cumsum(dtype=int64);m=M.cumsum(dtype=int64)
for K in query:
  x=d.copy();x[K:]-=d[:-K];x*=M
  x[K+1:]-=D[1:-K]*(m[K:-1]-m[:-K-1])
  print(sum(cumsum(x)*C))

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(b'-'+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):
    x = cumD.copy(); x[K:] -= cumD[:-K]
    x *= isM
    x[K+1:] -= isD[1:-K] * (cumM[K:-1] - cumM[:-K-1])
    return (x.cumsum() * isC).sum()

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

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 = D; DM *= isM
    # 左端の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
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
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:
n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))

def solve(k):
    cnt_d = 0
    cnt_m = 0
    ptn_dm = 0
    ans = 0
    for i in range(n):
        if s[i] == "D":
            cnt_d += 1
        if s[i] == "M":
            cnt_m += 1
            ptn_dm += cnt_d
        if s[i] == "C":
            ans += ptn_dm
        
        if i-k+1 >= 0:
            if s[i-k+1] == "D":
                cnt_d -= 1
                ptn_dm -= cnt_m
            if s[i-k+1] == "M":
                cnt_m -= 1
    return ans

for i in k:
    print(solve(i))

Submission status: Accepted

Solution code:
N =int(input())
S = input()
Q = int(input())
k = list(map(int, input().split()))
D = []
C = []
Sm = [0]*N
S1 = [0]*N

Sc = [0]*N
for i in range(N):
    if S[i] == 'D':
        D.append(i)
    elif S[i] == 'M':
        Sm[i] = 1
    elif S[i] == 'C': 
        C.append(i)
        S1[i] = 1
for i in range(1, N):
    Sm[i] = Sm[i-1]+Sm[i]
    S1[i] = S1[i-1]+S1[i]
for i in C:
    Sc[i] = Sm[i]
for i in range(1, N):
    Sc[i] = Sc[i-1]+Sc[i]
for ki in k:
    res = 0
    for d in D:
        end = min(d+ki-1,N-1)
        res+=Sc[end]-Sc[d]-(S1[end]-S1[d])*Sm[d]
    print(res)

Submission status: Accepted

Solution code:
def main():
    import sys,bisect
    input = sys.stdin.readline

    n = int(input())
    s = input()
    q = int(input())
    k_list = tuple(map(int,input().split()))
    
    for k in k_list:
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        ans = 0
        DMC = [0]*3
        for i in range(n):
            if s[i] == "D":
                DMC[0] += 1
            elif s[i] == "M":
                DMC[1] += 1
                DMC[2] += DMC[0]
            if i >= ki:
                j = i-ki
                if s[j] == "D":
                    DMC[0] -= 1
                    DMC[2] -= DMC[1]
                elif s[j] == "M":
                    DMC[1] -= 1
            if s[i] == "C":
                ans += DMC[2]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        ans = 0
        DMC = [0]*3
        for i in range(n):
            c = s[i]
            if c == "D":
                DMC[0] += 1
            elif c == "M":
                DMC[1] += 1
                DMC[2] += DMC[0]
            elif c == "C":
                ans += DMC[2]
            if i >= ki-1:
                j = i-ki+1
                if s[j] == "D":
                    DMC[0] -= 1
                    DMC[2] -= DMC[1]
                elif s[j] == "M":
                    DMC[1] -= 1
        print(ans)
if __name__ == "__main__":
    main()