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: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = [int(i) for i in input().split()]

# #%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]


#%%
idx_a = []
idx_b = []
idx_c = []

#%%
for i in range(len(s)):
    if s[i] == "D":
        idx_a.append(i)
    if s[i] == "M":
        idx_b.append(i)
    if s[i] == "C":
        idx_c.append(i)
        



#%%
for ki in k:
    ans = 0
    for a in idx_a:
        for c in idx_c:
            if a < c:
                if c - a < ki:
                    for b in idx_b:
                        if a<b:
                            if b<c:
                                ans += 1
                            else:
                                break
                else:
                    break
    print(ans)            

#%%

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0]
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc.append(c_cnt)

# print(a_loc)
# print(c_acc)

q = int(input())
for k in map(int, input().split()):
    ans = 0
    for b in b_loc:
        i = bisect.bisect_left(a_loc, max(0, b - k + 2))
        # print(b, i, a_loc[i])
        cn = c_acc[b]
        for a in a_loc[i:]:
            if a >= b:
                break
            ans += c_acc[min(a + k, n)] - cn
    print(ans)

Submission status: Time Limit Exceeded

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

for k in K:
    count = 0
    for a in range(len(S)-2):
        if S[a] == 'D':
            for b in range(a+1, len(S)-1):
                if S[b] == 'M':
                    for c in range(b+1, len(S)):
                        if S[c] == 'C':
                            if (c - a) < k:
                                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
S = raw_input()
Q = int(raw_input())
K = map(int, raw_input().split())

for k in K:
    count = 0
    prev_d = 0
    for i in range(S.count('D')):
        index_d = prev_d + S[prev_d:].index('D')
        prev_m = index_d
        for j in range(S[index_d:index_d+k].count('M')):
            index_m = prev_m + S[prev_m:index_d+k].index('M')
            count += S[index_m:index_d+k].count('C')
            prev_m = index_m+1
        prev_d = index_d+1

    print(count)

Submission status: Time Limit Exceeded

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

for kk in k:
    count = 0

    for a in range(n):
        if s[a] != 'D':
            continue
        for b in range(n):
            if s[b] != 'M':
                continue
            if a > b:
                continue
            for c in range(n):
                if s[c] != 'C':
                    continue
                if b > c:
                    continue
                if c - a >= kk:
                    continue
                
                count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
ki = list(map(int, input().split()))
DMC = []
for i in range(N):
    if S[i] == 'D':
        DMC.append((i, 1))
    elif S[i] == 'M':
        DMC.append((i, 2))
    elif S[i] == 'C':
        DMC.append((i, 3))

for i in range(len(ki)):
    num = 0
    for j in range(len(DMC)):
        for k in range(j, len(DMC)):
            for l in range(k,len(DMC)):
                if DMC[j][1] == 1 and DMC[k][1] == 2 and DMC[l][1] == 3 and (DMC[l][0] - DMC[j][0] < ki[i]):
                    num += 1
    print(num)

Submission status: Time Limit Exceeded

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

target = 'D'
index = -1
d_ = []
while True:
    index = s.find(target, index + 1)
    if index == -1:
        break
    d_.append(index)
target = 'M'
index = -1
m_ = []
while True:
    index = s.find(target, index + 1)
    if index == -1:
        break
    m_.append(index)
target = 'C'
index = -1
c_ = []
while True:
    index = s.find(target, index + 1)
    if index == -1:
        break
    c_.append(index)
for i in k:
    ans = 0
    for j in d_:
        for l in c_:
            if l-j<i:
                for m in m_:
                    if j<m and m<l:
                        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
S = input().strip()
Q = int(input().strip())
K = list(map(int, input().strip().split()))

for k in K:
  s = set()
  for i in range(len(S) - k + 1):
    subs = S[i: i + k]
    if 'D' not in subs or 'M' not in subs or 'C' not in subs:
      continue
    Dindex = [j for j, s in enumerate(subs) if s == 'D']
    Mindex = [j for j, s in enumerate(subs) if s == 'M']
    Cindex = [j for j, s in enumerate(subs) if s == 'C']
    for di in Dindex:
      for mi in Mindex:
        for ci in Cindex:
          if di < mi < ci and ci - di < k:
            s.add((di + i, mi + i, ci + i))
  print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())

d__ = [0]*(n+1)
dm_ = [0]*(n+1)
dmc = [0]*(n+1)
_m_ = [0]*(n+1)

def find_ans(k:int):
    ans = 0
    
    for i in range(1, n+1):
        d__[i] = d__[i-1]
        dm_[i] = dm_[i-1]
        dmc[i] = dmc[i-1]
        _m_[i] = _m_[i-1]
        
    
            
        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__[i] -= 1
                dm_[i] -= _m_[i]
                
            elif s[i-k+1] == 'M':
                _m_[i] -= 1
                
        if s[i] == 'D':
            d__[i] += 1    
        
        elif s[i] == 'M':
            dm_[i] += d__[i]
            _m_[i] += 1
            
        elif s[i] == 'C':
            ans += dm_[i-1]
            
    return ans
        
for ki in k:
    print(find_ans(ki))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
K = [int(i) for i in input().split()]

# flags_index = []
d_index = []
m_index = []
c_index = []
for i in range(N):
    if S[i] == 'D':
        d_index.append(i)
        # flags_index.append(1)
    elif S[i] == 'M':
        m_index.append(i)
        # flags_index.append(2)
    elif S[i] == 'C':
        c_index.append(i)
        # flags_index.append(3)
    # else:
        # flags_index.append(0)

for k_i in K:
    count = 0
    # c - a < k を満たす組み合わせ
    for d_i in d_index:
        for c_i  in c_index:
            if d_i < c_i and c_i - d_i < k_i:
                for m_i in m_index:
                    if d_i < m_i and m_i < c_i:
                        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
k=list(map(int,input().split()))
for i in range(q):
    p=s[:]
    h=0
    while p.count("D")!=0:
        f=p.index("D")
        p=p[f+1:]
        a=0
        m=(k[i]-1 if len(p)>=k[i]-1 else len(p))
        for c in range(m):
            if p[c]=="M":
                a+=1
            elif p[c]=="C":
                h+=a
    else:
        print(h)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ass = []
bs = []
cs = []
for i in range(n):
    w = s[i]
    if w == "D":
        ass.append(i)
    if w == "M":
        bs.append(i)
    if w == "C":
        cs.append(i)
ass.sort()
bs.sort()
cs.sort()
ass.reverse()
bs.reverse()
cs.reverse()
q = int(input())
ks = input().split()
count = 0
for i in range(q):
    k = int(ks[i])
    for x in range(len(ass)):
        for y in range(len(bs)):
            for z in range(len(cs)):
                a = ass[x]
                b = bs[y]
                c = cs[z]
                if (b >= c):
                    continue
                if (a >= b):
                    continue
                if (c-a >= k):
                    continue
                count += 1
    print(count)
    count = 0

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = [int(i) for i in input().split()]

# #%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]


#%%
idx_a = []
idx_b = []
idx_c = []

#%%
for i in range(len(s)):
    if s[i] == "D":
        idx_a.append(i)
    if s[i] == "M":
        idx_b.append(i)
    if s[i] == "C":
        idx_c.append(i)
        



#%%
for ki in k:
    ans = 0
    for a in idx_a:
        for c in idx_c:
            if a < c and c - a < ki:
                for b in idx_b:
                    if a<b and b<c:
                        ans += 1
            #         else:
            #             break
            # else:
            #     break
    print(ans)            

#%%

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

D=[]
M=[0 for _ in range(N)]
C=[]
DRC=[0 for _ in range(N)]

for i,x in enumerate(S):
    if x=='D':
        D.append(i)
    elif x=='M':
        M[i]=1
    elif x=='C':
        C.append(i)
M=list(accumulate(M))

for c in C:
    for d in D:
        if d>c:
            break
        DRC[c-d]+=M[c]-M[d]
DRC=list(accumulate(DRC))
for x in k:
    print(DRC[x-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
S = raw_input()
Q = int(raw_input())
K = map(int, raw_input().split())

for k in K:
    count = 0
    for i, s in enumerate(S):
        if s == 'D':
            if 0 <= S[i:i+k].count('M') and 0 <= S[i:i+k].count('C'):
                for j, s2 in enumerate(S[i:i+k]):
                    if s2 == 'M':
                        count += S[i+j:i+k].count('C')
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
k=list(map(int,input().split()))
for i in range(q):
    p=s[:]
    h=0
    while p.count("D")!=0:
        f=p.index("D")
        p=p[f+1:]
        w=p[:]
        w=w[:k[i]-1]
        l=w.count("C")
        kl=w.count("M")
        if l!=0and kl!=0:
            for qp in range(kl):
                j=w.index("M")
                w=w[j+1:]
                h+=w.count("C")
    else:
        print(h)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

#D=np.zeros(N,dtype='int32')
#M=np.zeros(N,dtype='int32')
M=[]
C=np.zeros(N,dtype='int32')

for i,s in enumerate(S):
    if s=='M': M.append(i)
    if s=='C': C[i:]+=1

for k in K:
    ans=0
    for i in range(N):
        if S[i]=='D':
            for j in range(i+1,min(i+k,N)):
                if S[j]=='M':
                    ans = ans + C[min(i+k,N)-1] - C[j]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ass = []
bs = []
cs = []
for i in range(n):
    w = s[i]
    if w == "D":
        ass.append(i)
    if w == "M":
        bs.append(i)
    if w == "C":
        cs.append(i)
q = int(input())
ks = input().split()
count = 0
for i in range(q):
    k = int(ks[i])
    for x in range(len(ass)):
        for y in range(len(bs)):
            for z in range(len(cs)):
                a = ass[x]
                b = bs[y]
                c = cs[z]
                if (a < b and b < c and c-a < k):
                    count += 1
    print(count)
    count = 0

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
K = [int(i) for i in input().split()]

d_index = []
m_index = []
c_index = []
for i in range(N):
    if S[i] == 'D':
        d_index.append(i)
    elif S[i] == 'M':
        m_index.append(i)
    elif S[i] == 'C':
        c_index.append(i)

for k_i in K:
    count = 0
    # c - a < k を満たす組み合わせ
    for d_i in d_index:
        for m_i in m_index:
            if d_i < m_i:
                for c_i in c_index:
                    if m_i < c_i and c_i - d_i < k_i:
                        count = count + 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
s = input()
q = int(input())
k_list = list(map(int,input().split()))

d_rec = []
m_rec = []
c_rec = []
for i, ss in enumerate(s):
    if ss == 'D':
        d_rec.append(i)
    if ss == 'M':
        m_rec.append(i)
    if ss == 'C':
        c_rec.append(i)
    

d_rec = np.array(d_rec)
m_rec = np.array(m_rec)
c_rec = np.array(c_rec)


dic = {}
for d in d_rec:
    for c in c_rec:
        if d > c:
            continue
        m = np.sum((m_rec < c) * (m_rec > d))
        if m > 0:
            try:
                dic[c - d] += m
            except:
                dic[c - d] = m

a = dic.keys()
a = np.array(list(a))

for k in k_list:
    key_here = a[a < k]
    su = 0
    for key in key_here:
        su += dic[key]
    print(su)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input())
S = list(input())
Q = int(input())

k_list = list(map(int, input().split()))

for q in range(Q):
	answer = 0

	for n in range(N):
		if S[n] == "D":
			for i in range(n, n + k_list[q]):
				if i < N:
					if S[i] == "M":
						for j in range(i, n + k_list[q]):
							if j < N:
								if S[j] == "C":
									answer += 1

	print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
K = [int(a) for a in input().split()]

for i in range(Q):
    k = K[i]
    ans = 0
    for i in range(1,N-1):
        if S[i] == "M":
            c = 0
            for j in range(1, k-1):
                if i+j<N:
                    if S[i+j] == "C":
                        c += 1
                if i+j-k>=0:
                    if S[i+j-k] == "C":
                        c -= 0
                if i+j-k+1 >= 0:
                    if S[i+j-k+1] =="D":
                        ans += c
                # print(i,i+j-k+1,i+j,c,ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
ki = list(map(int, input().split()))
D = []
M = []
C = []
for i in range(N):
    if S[i] == 'D':
        D.append(i)
    elif S[i] == 'M':
        M.append(i)
    elif S[i] == 'C':
        C.append(i)

for i in range(len(ki)):
    num = 0
    for j in range(len(D)):
        for k in range(len(M)):
            for l in range(len(C)):
                if (D[j] < M[k]) and (M[k] < C[l]) and (C[l] - D[j] < ki[i]):
                    num += 1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import numpy

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

pd = []
pm = []
pc = []
for i,s in enumerate(S):
	if s == 'D':
		pd.append(i)
	elif s =='M':
		pm.append(i)
	elif s =='C':
		pc.append(i)

for _k in k:
	cnt = 0
	for _pd in pd:
		for __pc in [_pc for _pc in pc if _pc < _k+_pd]:
			cnt += len([_pm for _pm in pm if _pm < __pc and _pm > _pd])
	print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

D = 0
for c in S:
    if c == 'D':
        D += 1

data0 = [0]*(D+1)
data1 = [0]*(D+1)
def _add(data, k, x):
    while k <= D:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

def solve(k):
    global data0, data1
    data0 = [0]*(D+1)
    data1 = [0]*(D+1)

    que = deque()
    res = 0
    l = r = 1
    for i, c in enumerate(S):
        while que and i-que[0] >= k:
            que.popleft()
            l += 1

        if c == 'D':
            r += 1
            que.append(i)
        elif c == 'M':
            add(l, r, 1)
        elif c == 'C':
            res += query(l, r)
    return res

*ans, = map(solve, K)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
s_list = list(input())
Q = int(input())
k_list = [int(a) for a in input().split()]

indexes_1 = [i for i, x in enumerate(s_list) if x == "D"]
indexes_2 = [i for i, x in enumerate(s_list) if x == "M"]
indexes_3 = [i for i, x in enumerate(s_list) if x == "C"]

for i in range(Q):
    k = k_list[i]
    indexes_4 = [(d, c) for d, c in itertools.product(indexes_1, indexes_3) if c > d > c - k]
    indexes_5 = [len([m for m in indexes_2 if a[0] < m < a[1]]) for a in indexes_4]
    print(str(sum(indexes_5)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
q = int(input())
k = [int(i) for i in input().split()]

#%%
# n = 54
# s = "DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED"
# q = 3
# k = [20, 30, 40]




#%%

for ki in k:
    ans = 0
    for a in range(n):
        if "D" == s[a]:
            for b in range(a, min(n, a+ki)):
                if "M" == s[b]:
                    for c in range(b, min(n, a+ki)):                    
                        if "C" == s[c]:
                            ans += 1

    print(ans)





#%%

Submission status: Time Limit Exceeded

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

class DMC:
    def __init__(self,k):
        self.ans=0
        self.k=k
        
    def searchC(self,i,t):
        for j in range(i,t):
            if S[j]=='C': self.ans+=1

    def searchM(self,i,t): #i文字目からt-1文字目までに見つける
        for j in range(i,t):
            if S[j]=='M': self.searchC(j+1,t)
            
    def __call__(self):    
        for i,s in enumerate(S):
            if s=='D':
                self.searchM(i+1,min(i+self.k,N))
        print(self.ans)


for k in K:
    DMC(k)()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    sa = []
    for c in s:
        if c == 'D':
            sa.append(1)
        elif c == 'M':
            sa.append(2)
        elif c == 'C':
            sa.append(3)
        else:
            sa.append(None)
    q = I()
    kk = LI()
    rr = []
    for k in kk:
        a = 0
        b = 0
        t = 0
        r = 0
        for j in range(k):
            if sa[j] is None:
                continue
            if sa[j] == 3:
                r += t
            elif sa[j] == 2:
                t += a
                b += 1
            else:
                a += 1
        for j in range(k,n):
            if sa[j-k] == 1:
                t -= b
                a -= 1
            elif sa[j-k] == 2:
                b -= 1

            if sa[j] is None:
                continue
            if sa[j] == 3:
                r += t
            elif sa[j] == 2:
                t += a
                b += 1
            else:
                a += 1

        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    for q in range(Q):
        k = K[q]
        res = 0
        cnt = [0] * 3
        for i in range(k):
            cur = S[i]
            if cur == "D":
                cnt[0] += 1
            elif cur == "M":
                cnt[1] += 1
                cnt[2] += cnt[0]
            elif cur == "C":
                res += cnt[2]

        for i in range(k, N):
            prev = S[i - k]
            cur = S[i]
            if prev == "D":
                cnt[0] -= 1
                cnt[2] -= cnt[1]
            elif prev == "M":
                cnt[1] -= 1

            if cur == "D":
                cnt[0] += 1
            elif cur == "M":
                cnt[1] += 1
                cnt[2] += cnt[0]
            elif cur == "C":
                res += cnt[2]
        print(res)


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:
    numD = 0
    numM = 0
    numDM = 0
    ans = 0
    for i in range(N):
        c = S[i]
        if c == 'D':
            numD += 1
        elif c == 'M':
            numM += 1
            numDM += numD
        elif c == 'C':
            ans += numDM

        if i >= k-1:
            c = S[i-k+1]
            if c == 'D':
                numD -= 1
                numDM -= numM
            elif c == 'M':
                numM -= 1
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Q = int(input())
K = [int(i) for i in input().split()]

for k in K:
    ans = 0

    d = m = dm = 0
    for i, si in enumerate(S):
        if 0 <= i - k:
            if S[i - k] == "D":
                d -= 1
                dm -= m
            elif S[i - k] == "M":
                m -= 1

        if si == "D":
            d += 1
        elif si == "M":
            m += 1
            dm += d
        elif si == "C":
            ans += dm

    print(ans)

Submission status: Accepted

Solution code:
n = int(input()) + 1
s = '?' + input()
q = int(input())
k = list(map(int,input().split()))

p_d = []
cnt_m = [0]*n
cnt_c = [0]*n

for i,si in enumerate(s[1:],1):
    cnt_m[i] = cnt_m[i-1]
    cnt_c[i] = cnt_c[i-1]
    if(si=='D'):
        p_d.append(i)
    elif(si=='M'):
        cnt_m[i] += 1
    elif(si=='C'):
        cnt_c[i] += 1

left_c = [0]*n
for i in range(1,n):
    left_c[i] = left_c[i-1]
    if(s[i]=='M'):
        left_c[i] += cnt_c[i]

# print(cnt_m)
# print(cnt_c)
# print(left_c)

ans = []
for ki in k:
    tmp = 0
    for di in p_d:
        x = cnt_m[min(di+ki-1,n-1)] - cnt_m[di-1]
        y = cnt_c[min(di+ki-1,n-1)]
        tmp += x*y - left_c[min(di+ki-1,n-1)] + left_c[di-1]
    ans.append(tmp)

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
S = input().strip()
Q = int(input())
K = list(map(int,input().split()))

'''
import random
import string
S = "".join(random.choices(string.ascii_uppercase, k=10**6))
Q =75 
K = [random.randint(1,10**6) for i in range(Q)]
'''

for k in K:
    ans = 0
    m = [0] * 3
    for i,s in enumerate(S):
        if i >= k:
            pre = S[i-k]
            if pre == 'D':
                m[0] -= 1 # m['D'] -= 1
                m[2] -= m[1] # m['DM'] -= m['M']
            elif pre == 'M':
                m[1] -= 1 # m['M'] -= 1
        if s == 'D':
            m[0] += 1 # m['D'] += 1
        if s == 'M': 
            m[2] += m[0] # m['DM'] += m['D']
            m[1] += 1# m['M'] += 1
        if s == 'C':
            ans += m[2] # ans += m['DM']
        #print(s,m)
    print(ans)

Submission status: Accepted

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

for k in K:
    ANS=0
    D=M=DM=0
    
    for i in range(N):
        if i-k>=0:
            if S[i-k]=="D":
                D-=1
                DM-=M
            elif S[i-k]=="M":
                M-=1

        if S[i]=="D":
            D+=1
        elif S[i]=="M":
            DM+=D
            M+=1
        elif S[i]=="C":
            ANS+=DM

    print(ANS)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
S = LS2()
Q = I()
K = LI()


def query(k):
    res = 0
    a = 0  # (i-k,i] にあるDの個数
    b = 0  # (i-k,i] にあるMの個数
    c = 0  # (i-k,i] にある(D,M)の個数
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                a -= 1
                c -= b
            elif S[i-k] == 'M':
                b -= 1
        if S[i] == 'D':
            a += 1
        elif S[i] == 'M':
            b += 1
            c += a
        elif S[i] == 'C':
            res += c
    return res


print(*[query(k) for k in K],sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())
kl = list(map(int, input().split()))
ansl = []
for k in kl:
    d_cnt = 0
    m_cnt = 0
    c_cnt = 0
    dm_cnt = 0
    dmc_cnt = 0
    for i in range(k):
        si = s[i]
        if si == 'D':
            d_cnt += 1
        elif si == 'M':
            m_cnt += 1
            dm_cnt += d_cnt
        elif si == 'C':
            c_cnt += 1
            dmc_cnt += dm_cnt   
    
    rem = n-k
    for i in range(rem):
        drop = s[i]
        new = s[i+k]
        if drop == 'D':
            d_cnt -= 1
            dm_cnt -= m_cnt
        elif drop == 'M':
            m_cnt -= 1
        elif drop == 'C':
            c_cnt -= 1
        
        if new == 'D':
            d_cnt += 1
        elif new == 'M':
            m_cnt += 1
            dm_cnt += d_cnt
        elif new == 'C':
            c_cnt += 1
            dmc_cnt += dm_cnt

    ansl.append(dmc_cnt)

for a in ansl: print(a)

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()))

ans = []
for k in K:
    d = m = dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)
print(*ans, sep='\n')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
   
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 = [func(ch) for ch in S]

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))