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

Solution (Python):
n = int(input())
s = input()
acc_cnt_a = [0] * n
acc_cnt_b = [0] * n
acc_cnt_ab = [0] * n
c_loc = []
cnt_a = 0
cnt_b = 0
cnt_ab = 0
for i in range(n):
    c = s[i]
    if c == 'D':
        cnt_a += 1
    elif c == 'M':
        cnt_b += 1
        cnt_ab += cnt_a
    elif c == 'C':
        c_loc.append(i)
    acc_cnt_a[i] = cnt_a
    acc_cnt_b[i] = cnt_b
    acc_cnt_ab[i] = cnt_ab

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l >= 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Solution (Python):
n = int(input())
s = input()
acc_cnt_a = [0] * n
acc_cnt_b = [0] * n
acc_cnt_ab = [0] * n
c_loc = []
cnt_a = 0
cnt_b = 0
cnt_ab = 0
for i, c in enumerate(s):
    if c == 'D':
        cnt_a += 1
    elif c == 'M':
        cnt_b += 1
        cnt_ab += cnt_a
    elif c == 'C':
        c_loc.append(i)
    acc_cnt_a[i] = cnt_a
    acc_cnt_b[i] = cnt_b
    acc_cnt_ab[i] = cnt_ab

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l >= 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Solution (Python):
n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
cnt_b = 0
cnt_ab = 0
for i, c in enumerate(s):
    if c == 'D':
        cnt_a += 1
    elif c == 'M':
        cnt_b += 1
        cnt_ab += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
    acc_cnt_a[i + 1] = cnt_a
    acc_cnt_b[i + 1] = cnt_b
    acc_cnt_ab[i + 1] = cnt_ab

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

Solution (Python):
from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))

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

def Counter(S, k):
    Total = 0
    count = [0, 0, 0] 
    for i in range(N):
        
        if S[i] == "D": count[0] += 1
        elif S[i] == "M": 
            count[1] += + 1
            count[2] += count[0]
        elif S[i] == "C":
            Total += count[2]
        if i >= k - 1:
            if S[i-k+1] == "D":
                count[0] -= 1
                count[2] -= count[1]
            elif S[i-k+1] == "M":
                count[1] -= 1
    return Total

for i in range(Q):
    print(Counter(S, K[i]))

Solution (Python):
import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    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')

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

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)

Solution (Python):
def solve():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(int, input().split()))

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

            if i >= k - 1:
                if s[i - k + 1] == 'D':
                    cnt -= m
                    d -= 1
                elif s[i - k + 1] == 'M':
                    m -= 1

        print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    N = int(input())
    S = input()
    Q = int(input())
    K = list(map(int, input().split()))
    for k in K:
        d_cnt = 0
        m_cnt = 0
        dm_cnt = 0
        answer = 0
        for i in range(N):
            c = S[i]
            if i-k >= 0:
                prevc = S[i-k]
                if prevc == "D":
                    d_cnt -= 1
                    dm_cnt -= m_cnt
                elif prevc == "M":
                    m_cnt -= 1
            if c == "D":
                d_cnt += 1
            elif c == "M":
                m_cnt += 1
                dm_cnt += d_cnt
            elif c == "C":
                answer += dm_cnt
        print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Solution (Python):
import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
dp = [0,0,0,0]
dp1 = [0,0,0,0]
for i in k:
  dp = [1,0,0,0]
  for j in range(n):
    dp1 = dp
    kon = x[j]
    if kon:
      dp1[kon] += dp[kon-1]
    dp = dp1
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[1] -= 1
        dp[2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp1[3])

Solution (Python):

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

res = 0


C_cnt = [0]*N
M_cnt = [0]*N
MC_cnt = [0]*N

M = 0
C = 0
MC = 0

for i in range(N):
    if S[i] == "M":
        M += 1
    if S[i] == "C":
        C += 1
        MC += M
    C_cnt[i] = C
    M_cnt[i] = M
    MC_cnt[i] = MC
    
res_list = [0]*Q

for q in range(Q):
    k = k_list[q]
    res = 0
    for i in range(N):
        if S[i] == "D":
            j = min(i + k - 1, N - 1)
            res += MC_cnt[j] - MC_cnt[i] - (C_cnt[j] - C_cnt[i]) * M_cnt[i]
    res_list[q] = res
    
for r in res_list:
    print(r)

Solution (Python):
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())