Problem:


Score : 500 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.

Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

Constraints

All values in input are integers.

1 \leq N \leq 2\times 10^5

1 \leq K \leq 10^9

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

Print the number of subsequences that satisfy the condition.

Sample Input 1

5 4
1 4 2 3 5

Sample Output 1

4

Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).

Sample Input 2

8 4
4 2 4 2 4 2 4 2

Sample Output 2

7

(4,2) is counted four times, and (2,4) is counted three times.

Sample Input 3

10 7
14 15 92 65 35 89 79 32 38 46

Sample Output 3

8



Sample input:
5 4
1 4 2 3 5


Sample output:
4

Submission status: Time Limit Exceeded

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

sl = [0 for _ in range(N+1)]

for i in range(N):
    sl[i+1] = (sl[i]+ls[i]-1)%K
ans = 0

dic = {}

for i in range(K):
    dic[i] = 0

que = []

for i in range(N+1):
    ans += dic[sl[i]]
    dic[sl[i]] += 1
    que.append(sl[i])
    if len(que) == K:
        dic[que[0]] -= 1
        que.pop(0)

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(0, len(ls)):
    for j in range(i+1, len(ls)+1):
        tg = ls[i:j]
        if sum(tg)%K == len(tg):
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
n,k = map(int,input().split())
l = list(map(int,input().split()))
ans = 0
now = 0
for i in range(1,len(l)+1):
    deq = collections.deque(maxlen = i)
    for j in range(len(l)):
        deq.append(l[j])
        if len(deq) == i:
            now = sum(deq)
            if now%k == len(deq):
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
ans = 0
now = 0
for i in range(1,len(l)+1):
    for j in range(len(l)):
        if len(l[j:j+i]) == i:
            now = sum(l[j:j+i])
            if now%k == i:
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    d = {}
    d2 = {}
    d[0] = [0]
    s = 0
    for i in range(1, N+1):
        s = (s + A[i-1]) % K
        t = (s-i) % K
        if t in d:
            d[t].append(i)
        else:
            d[t] = [i]
        d2[i] = t
    a = 0
    for i in range(1, N+1):
        for j in d[d2[i]]:
            if i - K < j and j < i:
                a += 1
            if j >= i:
                break
    return a

print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    d = {}
    d2 = {}
    d[0] = [0]
    s = 0
    for i in range(1, N+1):
        s = s + A[i-1]
        t = (s-i) % K
        if t in d:
            d[t].append(i)
        else:
            d[t] = [i]
        d2[i] = t
    a = 0
    for i in range(1, N+1):
        for j in d[d2[i]]:
            if i - K < j and j < i:
                a += 1
    return a

print(main())

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(N):
  x=a[i]
  if a[i]%K==1:
    ans+=1
  j=i+1
  while j<=N-1 and j-i+1<=K-1:
    x+=a[j]
    if x%K==j-i+1:
      ans+=1
    j+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import defaultdict
import sys

def input(): return sys.stdin.readline().strip()

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Time Limit Exceeded

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

A = [0 for _ in range(N)]
for i, a in enumerate(input().split()):
    A[i] = int(a) % K

result = 0
for i in range(N):
    now = 0
    for j in range(i, N):
        now += A[j]

        if now % K == j-i+1:
            result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m] #1列の数列をリスト化
n = input()    
m = n.split()
P = [int(i) for i in m] #1列の数列をリスト化
from collections import deque
list = deque([0])
for i in P:
    a = (list[-1] + i - 1) % p[1]
    list.append(a)
list.popleft()
search = deque([])
A = 0
for i in range(p[0]):
    if i >= p[1]:
        search.popleft()
    a = list.popleft()
    if a == 0 and i < p[1]-1:
        A = A + 1
    A = A + search.count(a)
    search.append(a)
print(A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque


def p_e():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    dp = np.array([0] * n)
    q = deque([-1] * n)
    ans = 0
    for i in range(n):
        q.appendleft(i + 1)
        q.pop()
        c = a[i] % k
        dp[:i + 1] += c
        dp[:i + 1] %= k
        ans += (dp == q).sum()
    print(ans)
    
p_e()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque


def p_e():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    dp = np.array([0] * n)
    q = deque()
    ans = 0
    for i in range(n):
        q.appendleft(i + 1)
        c = a[i] % k
        now_dp = dp[:i + 1]
        now_dp += c
        now_dp %= k
        ans += np.sum(now_dp == q)
    print(ans)

p_e()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import bisect
import array

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
i = 0 
for b in B:
    x = (x + b ) % K 
    C.append((x-i-1) % K) 
    i += 1 
    
# print(B,C)

E=[0 for _ in range(K)] 


ans=0
for i in range(N+1):
    ans += E[C[i]]
    if i >= K-1:
        E[C[i-K+1]] -= 1
    # print(i,C[i],ans,E)
    E[C[i]]+=1
print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
#尺取り法と累積和
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
for i in range(k):
    count[i] = 0
q = deque()
for i in acc_a:
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N,K) = map(int,input().split())
A = list( map(int,input().split())) 
# print(N,K,A)
B = list( map(lambda x: x % K, A))
C = [0]
x = 0
for b in B:
    x = (x + b ) % K 
    C.append(x)
    
# print(B,C)

ans=0
for i in range(N):
    for j in range(i,N):
        # print(i,j)
        # print(A[i:j+1],C[i],C[j+1],(C[j+1]-C[i]) % K)
        if (C[j+1]-C[i]) % K == j-i+1:
            ans = ans + 1 
print(ans)

exit(0)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(n):
    for j in range(n-i):
        part = 0
        for l in range(i+1):
            part += a[l+j]
        if part%k == i+1:

            count += 1

print(count)

Submission status: Time Limit Exceeded

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

import sys
N_K = list(map(int, input().split()))
A_row = list(map(int, input().split()))
#A_row[N_K[0]+1]=0
#A_row.append(0)#要素をA_rowの右端に追加
#print(A_row)
N=N_K[0]
k=N_K[1]
#print(k)
i=0
j=0
l=0
somesum=0
num=0
#somesum=sum(A_row)#リスト内の要素を全て足し合わせる
for i in range(N_K[0]):#個数の階乗の部分を表す。   
 for j in range(N_K[0]-i):
   #print(N_K[0]-i, N_K[0]-i-j+1, N-j)
   #print(N_K[0]-i, N-j, j)
   #print((A_row[0:N-j-i]))
   num=N-j-i
   #print("要素数"+str(num))
   #print((A_row[0:N-j-i]))
   somesum=sum(A_row[0:N-j-i])
   #print(somesum)

   if somesum%k==N-j-i:
      l = l+1
      #print(A_row[0:N-j-i])
      #print("要素数"+str(num))
      #print((A_row[0:N-j-i]))
   else:
       pass

 del A_row[0]
# print(A_row)

print(l)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Nov 29 05:05:16 2019

@author: matsui
"""
import numpy as np

N,K=map(int,input().split())
A=input().split()
A=np.array(A,dtype=int)


count=0
for i in range(1,N+1):
    if i >= K: break
    for j in range(N):
        if i+j>N:break
        S=A[j:j+i].sum()
        if S%K == i: count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Nov 29 05:05:16 2019

@author: matsui
"""
import numpy as np

N,K=map(int,input().split())
A=input().split()
A=np.array(A,dtype=int)


count=0
for i in range(1,N+1):
    for j in range(N):
        if i+j>N:break
        S=A[j:j+i].sum()
        if S%K == i: count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Nov 29 05:05:16 2019

@author: matsui
"""

def sumA(A):
    S=0
    L=len(A)
    for i in range(L):
        S+=int(A[i])
    return S
  
N,K=map(int,input().split())
A=input().split()

count=0
for i in range(1,N+1):
    for j in range(N):
        if i+j>N:break
        S=sumA(A[j:j+i])
        if S%K == i: count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
S = np.cumsum(A)

answer = 0
for j in range(N):
    for i in range(j+1,min(N+1, K+j)):
        if (S[i]- S[j]) % K == (i-j):
            answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# coding: utf-8

def IsIt(): return map(lambda x: int(x), input().split())

def IsIl(): return list(map(lambda x: int(x), input().split()))

n,k=IsIt()

a = IsIl()

ans = 0

sum_1 = 0
for num1, item1 in enumerate(a): #要素数
    if num1+1>=k: break
    sum_1 += item1
    if sum_1%k == num1+1: ans += 1
    # for num2, item2 in enumerate(a):
    sum_n = sum_1
    for num2 in range(n-num1-1):
        sum_n = sum_n + a[num1+num2+1] - a[num2]
        if sum_n%k == num1+1: ans += 1



            
        
        
        
        
        
    



# dp1 = []
# les = 0
# for num,item in enumerate(a):
#     les = (les + item)%k
#     if les == num+1: ans += 1
#     dp1.append(les)
    

# for num1 in range(n-1):
#     dp2 = []
#     for num, item in enumerate(dp1):
#         if num < 1: continue
#         les = (item - a[num1])%k
#         if les == num: #  and num-num1 >= 1:
#             ans += 1
#         dp2.append(les)

#     dp1 = dp2[:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
for i in range(N):
  Alen=0
  Asum=0
  for j in range(i,N):
    if i==j:
      Alen=1
      Asum=A[j]
    else:
      Alen+=1
      Asum+=A[j]
    if Asum%K==Alen:
      cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# coding: utf-8

def IsIt(): return map(lambda x: int(x), input().split())

def IsIl(): return list(map(lambda x: int(x), input().split()))

n,k=IsIt()

a = IsIl()

ans = 0

dp1 = []
les = 0
for num,item in enumerate(a):
    les = (les + item)%k
    if les == num+1: ans += 1
    dp1.append(les)
    

for num1 in range(n-1):
    dp2 = []
    for num, item in enumerate(dp1):
        if num < 1: continue
        les = (item - a[num1])%k
        if les == num: #  and num-num1 >= 1:
            ans += 1
        dp2.append(les)

    dp1 = dp2[:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [i-1 for i in A]
sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from collections import defaultdict

def cmb_2(n):
    return n*(n-1)//2

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [i-1 for i in A]
sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    ans += cmb_2(modmap[i])

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# coding: utf-8

# 整数 > 整数型
def I(): return int(input())

# 整数列 '1 2 3 4' > 整数型リスト
def IsIl(): return list(map(lambda x: int(x), input().split()))

# 改行挟む整数列　'1/n 2/n 3/n' > 整数型りすと
def InIl(n): return [input() for i in range(n)]

# 整数列 '1 2' > 整数型タプル
def IsIt(): return map(lambda x: int(x), input().split())

# 改行挟む整数列　'1\n 2\n 3\n' > 整数型たぷる
def InIl(n): return map(input() for i in range(n))

# 文字列 'abcd' > 文字型リスト
def SsSl(): return list(map(lambda x: x, input()))

# 整数 '1234' > 整数型リスト

# 文字列 'aba' > 辞書（文字型:個数）{'a':2,'b':1}
def SSd():
    from collections import defaultdict
    A = input() # [int(i) for i in input().split()]
    dd=defaultdict(int)
    for a in A:
        dd[a]+=1
    return dd

n,k=IsIt()

a = IsIl()

ans = 0

dp1 = []
les = 0
for num,item in enumerate(a):
    les = (les + item)%k
    if les == num+1: ans += 1
    dp1.append(les)
    

for num1 in range(n-1):
    dp2 = []
    for num, item in enumerate(dp1):
        les = (item - a[num1])%k
        if les == num-num1 and  num-num1>=1:
            ans += 1
        dp2.append(les)

    dp1 = dp2[:]

print(ans)

Submission status: Time Limit Exceeded

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

#input
N, K = map(int, input().split())
A = list(map(int, input().split()))

#output
import numpy as np

B = np.cumsum(A)

answer = 0
for i in range(N):
    answer += len([j % K  for i, j in enumerate(B) if  j % K == i+1])
    B = np.delete(B - B[0], 0)
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#input
N, K = map(int, input().split())
A = list(map(int, input().split()))

#output
import numpy as np

B = np.cumsum(A)

answer = 0
for i in range(N):
    answer += len([j % K  for i, j in enumerate(B) if  j % K == i+1])
    B -= B[0]
    B = np.delete(B, 0)
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]

# 2D dynamic programming solution using 2 rows
dp = [[0]*(N) for i in range(2)]
dp[0] = A

num_seq = 0

for a in A:
    if (a % K) == 1:
        num_seq += 1

# pass through a single row first
for i in range(1, N): # i = row
    for j in range(i, N): # j = col
        if i == 1:
            subseq_total = sum(A[j-1:j+1])
        else:
            subseq_total = dp[0][j-1] + A[j]
        dp[1][j] = subseq_total
        if (subseq_total % K) == (i+1):
            num_seq += 1
    dp[0] = dp[1]
    dp[1] = [0]*N

#for row in dp:
#    print(row)

print(num_seq)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]

# 2D dynamic programming solution?
dp = [[0]*(N) for i in range(N)]
dp[0] = A

num_seq = 0

for a in A:
    if (a % K) == 1:
        num_seq += 1

for i in range(1, len(A)):
    for j in range(1,i+1):
        if j == 1:
            subseq_total = sum(A[i-j:i+1])
            dp[j][i] = subseq_total
        else:
            subseq_total = dp[j-1][i-1] + A[i]
        dp[j][i] = subseq_total
        if (subseq_total % K) == (j+1):
            num_seq += 1

#for row in dp:
#    print(row)

print(num_seq)

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si
	
	count=0
	for j in range(n+1):
		sj=sss[j]
		for i in range(max(0, j-k+1), j):
			si=sss[i]
			if (sj - si) % k == 0:
				pa((i,j))
				count+=1
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
def f(x):
	return x%k

nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])
a = input().split(' ')
a = list(map(int,a))
#a = list(map(f,a))

sum = 0
temp_k_array = [0]
temp_k_dict = {}
for i in range(k):
	temp_k_dict[i] = 0
temp_k_dict[0] = 1

count = 0
for i, x in enumerate(a):
	sum += x
	if i+1>k-1:
		p = temp_k_array.pop(0)
		temp_k_dict[p] -= 1
	t = (sum-i-1)%k
	count += temp_k_dict[t]
	temp_k_array.append(t)
	temp_k_dict[t] += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A) % k
S = np.copy(A)
ans = (A == 1).sum()
for n in range(1, len(A)):
    if n == k:
        break
    S[n:] = (S[n:] + A[:-n]) % k
    ans += (S[n:] == n + 1).sum()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(x):
	return x%k

nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])
a = input().split(' ')
a = list(map(int,a))
a = list(map(f,a))
sum = 0
s = [0]
for i in a:
	sum += i
	s.append(sum)
# s = list(map(f,s))

count = 0
for i in range(0,n):
	m = i+k+1
	if i+k > n:
		m = n+1
	for j in range(i+1,m):
		if (s[j]-s[i])%k == j-i:
			count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	count=0
	for i in range(1, min(n, k)+1):
		#pa(i)
		aa=sum(aal[:i])
		if aa % k == i:
			count+=1
		for j in range(n-i):
			aa += aal[i+j]
			aa -= aal[j]
			count+=(aa % k == i)
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	count=0
	for i in range(1, min(n, k)+1):
		#pa(i)
		aa=sum(aal[:i])
		if aa % k == i:
			count+=1
		for j in range(n-i):
			aa += aal[i+j]
			aa -= aal[j]
			count+=(aa % k == i)
	
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

an = [a % k for a in an]
cnt = 0
for i in range(1, n+1):
  sm = sum(an[:i])
  if sm % k == i:
    cnt += 1
  for j in range(i, n):
    sm += (an[j] - an[j-i])
    if sm % k == i:
      cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(i) % K for i in input().split()]

W = [0] * (N + 1)

for i in range(N):
    W[i + 1] = W[i] + A[i]

cnt = 0
for i in range(N):
    for j in range(i, min(i + K, N)):
        if (W[j + 1] - W[i]) % K == (j - i + 1):
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

W = [0] * (N + 1)

for i in range(N):
    W[i + 1] = W[i] + A[i]

cnt = 0
for i in range(N):
    for j in range(i, min(i + K, N)):
        if (W[j + 1] - W[i]) % K == (j - i + 1):
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = input().split()
N,K = int(N),int(K)
A = list(map(int,input().split()))
S_j = [0 for i in range(N+1)]
per_Ks = np.array([0 for i in range(N+1)])

def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    S_j[j] = S_j_
    
    per_K = (S_j_-j)%K
    per_Ks[j] = per_K
    
    max_ = max([0,j-K+1])
    count += (per_Ks[max_:j]==per_K).sum()
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,K = input().split()
N,K = int(N),int(K)
A = list(map(int,input().split()))
S_j = [0 for i in range(N+1)]

def f(j,S_j):
    return S_j%K-j 

i,j = 0,1
S_j_ = 0
count = 0

for j in range(1,N+1):
    j_ = j-1
    S_j_ += A[j_]
    S_j[j] = S_j_
    
    per_K = (S_j_-j)%K
    
    max_ = max([0,j-K+1])
    for i in range(max_,j):
        if((S_j[i]-i)%K == per_K):
            count += 1
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=[]
m2=[0]
for i in range(n):
  m.append(a[i])
for i in range(n):
  m2.append((m2[-1]+m[i]))
for i in range(n+1):
  m2[i]-=i
  m2[i]%=k

ans=0
dict={}
for i in range(1,n+1):
  x=m2[i]
  if i<=k-1:
    dict[i-1]=m2[i-1]
  else:
    dict[i-1]=m2[i-1]
    del dict[i-k]
  d=collections.Counter(dict.values())
  ans+=d[x]
print(ans)

Submission status: Time Limit Exceeded

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

l,r = 0,1
count = 0
while(l<N):
    r = l+1
    while(r<=N):
        sum_ = sum(A[l:r])
        if(sum_%K==r-l):
            count += 1
        r+=1
    l += 1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    B=[0]*N
    ans=0
    for i in range(N):
        B[i]=A[i]%K
        z=B[i]
        for j in range(min(K-1,i+1)):
            if z==j+1:
                ans+=1
            z+=B[i-(1+j)]
            z%=K
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]
for Ai in A:
    B.append((B[-1]+Ai-1)%K)
# print(B) #DB

C=[[] for i in range(K)]
for i in range(N+1):
    C[B[i]].append(i)
# print(C) #DB

ans=0
for Ci in C:
    m=len(Ci)
    if m<2:
        continue
    l,r=0,1
    while True:
        if Ci[r]-Ci[l]<K:
            ans+=1
            if r<m-1:
                r+=1
            else:
                if l==m-2:
                    break
                else:
                    l+=1
                    r=l+1
        else:
            if l==m-2:
                break
            else:
                l+=1
                r=l+1

print(ans)

Submission status: Time Limit Exceeded

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

N,K,*A = map(int,read().split())
 
A = [0] + [x-1 for x in A]
B = list(itertools.accumulate(A))
B = [x % K for x in B]
count=0
for i in range(N):
  for j in range(i+1,N+1):
    if j-i==K:
      break
    elif (B[j]-B[i])%K==0:
      count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N,K =map(int,input().split())
A = np.array([int(x) for x in input().split()])
A=(A-1)%K
B=np.concatenate([[0],np.cumsum(A)])#(N+1)項、Aの累積和
count=0
for i in range(N):
  for j in range(i+1,N+1):
    if j-i==K:
      break
    elif (B[j]-B[i])%K==0:
      count +=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N,K =map(int,input().split())
A = np.array([int(x) for x in input().split()])
A=A-1
B=np.concatenate([[0],np.cumsum(A)])#(N+1)項、Aの累積和
count=0
for i in range(N):
  for j in range(i+1,N+1):
    if j-i==K:
      break
    elif (B[j]-B[i])%K==0:
      count +=1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  for j in range(i+1,N+1):
    if sum(A[i:j])%K == len(A[i:j]):
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))

ans = 0
for l in range(N):
    for r in range(l+1, min(l+K, N+1)):
        if r % K == (A_acc[r]-A_acc[l]+l) % K:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#尺取り法と累積和
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [i % k for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0]
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
#print(acc_a)
ans = 0
for i in range(len(acc_a)):
    for j in range(max(0, i - k), i):
        #print("i {}  j {}".format(i,j))
        list_sum = acc_a[i] - acc_a[j]
        if list_sum < 0:
            list_sum += k
        if i - j == list_sum:
            #print("i {}  j {}".format(i,j))
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#尺取り法と累積和
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [i % k for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0]
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k

"""
#尺取り法、
right = 1
left = 0
ans = 0
while right != len(acc_a) or right != left:
    print("l{}  r{}".format(left, right))
    #選んだ配列の個数
    list_num = 1 + right - left
    #選ぶ配列長さがkより大きいことはない
    if list_num >= k:
        left += 1
    #左が追い付いたら右を増やす
    if right == left:
        right += 1
    sum_list = acc_a[right] - acc_a[left]
    if sum_list < 0:
        sum_list += k
    
    if sum_list == list_num:
        ans += 1
        right += 1
    else:
        left += 1
"""
#print(acc_a)
ans = 0
for i in range(len(acc_a)):
    for j in range(max(0, i - k), i):
        #print("i {}  j {}".format(i,j))
        if i - j > k:
            break
        list_sum = acc_a[i] - acc_a[j]
        if list_sum < 0:
            list_sum += k
        if i - j == list_sum:
            #print("i {}  j {}".format(i,j))
            ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1 and str(S2[j-K]) in d:
        d[str(S2[j-K])] -= 1
        
    if str(S2[j-1]) in d:
        d[str(S2[j-1])] += 1
    else:
        d[str(S2[j-1])] = 1
        
    if str(S2[j]) in d:
        ans += d[str(S2[j])]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        d[str(S2[j-K])] = d.get(str(S2[j-K]), 0) - 1
    d[str(S2[j-1])] = d.get(str(S2[j-1]), 0) + 1
    ans += d.get(str(S2[j]), 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = [int(x) for x in input().split()]

cnt = 0
for i in range(N):
    s = [0] * (N+1)
    for j in range(N-i):
        s[j+1+i] = a[j+i] + s[j+i]
        if s[j+1+i] % K == j+1:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    temp = 0
    for j in range(i,N):
        temp += A[j]
        if j-i+1 >= K:
            break;
        if temp%K == j-i+1:
            cnt += 1
print (cnt)