One of the search methods. Since the number of calculations is smaller than that of the full search, the speed of the search can be increased. As the name of cumulative sum, we use a table created by accumulating sums. Show the actual past questions of Atcoder and the solution by Python to deepen the knowledge of cumulative sum.
Problem: ABC037-C-Sum Given a sequence of length N {ai} and an integer K greater than or equal to 1 and less than or equal to N. This sequence has N−K + 1 contiguous subcolumns of length K. Find the sum of the values in each of these subcolumns.
ruisekiwa.py
N,K = map(int, input().split())
a = list(map(int, input().split()))
#N,K = 5,3
#a = [1, 2, 4, 8, 16]
#1.mt:Cumulative sum table
mt = [0]
for i, aa in enumerate(a):
mt.append(mt[i] + aa)
#mt=[0, 1, 3, 7, 15, 31]
ans = 0
for i in range(K,N+1):
ans += (mt[i]-mt[i-K])
print(ans)
As an example, consider ai = [1, 2, 4, 8, 16], N = 5, K = 3. In this example, it is possible to calculate steadily using the for statement, but the amount of calculation increases as the input value increases, so the calculation is performed using accumulation. As a general solution
Problem: ABC172C --Tundoku There are two desks A and B. Desk A has N books stacked vertically, and desk B has M books stacked vertically. The i-th book currently loaded on desk A (1 ≤ i ≤ N) takes Ai minutes to read, and the i-th book currently loaded on desk B (1 ≤ i ≤ N) M) takes Bi minutes to read. Consider the following actions. Select the desk where the books remain, read the books on top of the desk, and remove them from the desk. How many books can you read when you repeat this action so that the total travel time does not exceed K minutes? Ignore the time it takes other than reading a book.
ABC172C.py
N,M,K = 3,4,1
A=[60,90,120]
B=[80,150,80,150]
ans=0
sum_A=[0]*(N+1)
sum_B=[0]*(M+1)
for i in range(1,N+1):
sum_A[i] = sum_A[i-1] + A[i-1]
for j in range(1,M+1):
sum_B[j] = sum_B[j-1] + B[j-1]
b=M
for a in range(N+1):
if sum_A[a]>K:
break
while sum_B[b] > K-sum_A[a]:
b-=1
ans = max(ans, a+b)
print(ans)
If you add each time, you can search efficiently by using LTE and index using cumulative sum.
ABC134-C - Exception Handling Given the sequence A1, A2, ..., AN of length N. Answer the following questions for each integer i greater than or equal to 1 and less than or equal to N. Find the maximum value of N-1 elements excluding Ai in the sequence.
ABC134C.py
N = 3
a = [1,4,3]
#Prepare an array to store the maximum value at the location to the left of i and the maximum value at the location to the left of i
left_max = [0]*N
right_max = [0]*N
for i in range(1,N):
left_max[i] = max(left_max[i-1],a[i-1])
#[0, 1, 4]
right_max[N-i-1] = max(right_max[N-i],a[N-i])
#[4, 3, 0]
#Solved by passing the maximum value for each element of 2 arrays
for j in range(N):
print(max(left_max[j], right_max[j]))
ARC098C - Attention N people are lined up in a row in the east-west direction. Each person is facing east or west. Who is facing in which direction is given by the string S of length N. The i-th line from the west faces east if Si = E and west if Si = W. You appoint one of the N as a leader. Then instruct everyone except the leader to look in the direction of the leader. At this time, the leader may be facing in either direction. People in line don't like to turn around. Therefore, you want to choose a leader that minimizes the number of people turning. Find the minimum number of people who can change their direction.
ABC098C.py
N = 12
s = "WEWEWEEEWWWE"
WL_num = [0]*N
ER_num = [0]*N
for i in range(1,N):
if s[i-1] == 'W':
WL_num[i] = WL_num[i-1] + 1
else:
WL_num[i] = WL_num[i-1]
if s[N-i] == 'E':
ER_num[N-i-1] = ER_num[N-i] + 1
else:
ER_num[N-i-1] = ER_num[N-i]
#WL_num:[0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5, 6]
#ER_num:[6, 5, 5, 4, 4, 3, 2, 1, 1, 1, 1, 0]
ans = float('inf')
for i in range(N):
ans = min(ans, WL_num[i]+ER_num[i])
print(ans)
The above problem + cumulative sum.
ABC125C - GCD on Blackboard N integers A1, A2, ..., AN are written on the blackboard. You can choose one of these integers and rewrite it with any integer between 1 and 109. You can rewrite it to the same integer as the original integer. Find the greatest common divisor of N integers after rewriting.
ABC125C.py
import math
N = 3
a = [7,6,8]
#The greatest common divisor of the set on the left side of i is lgcd,Store the greatest common divisor on the right in rgcd
lgcd = [0]*N
lgcd[0]=a[0]
rgcd = [0]*N
rgcd[N-1] = a[N-1]
for i in range(1,N):
lgcd[i] = math.gcd(lgcd[i-1], a[i-1])
rgcd[N-i-1] = math.gcd(rgcd[N-i],a[N-i])
#lgcd=[7, 7, 1]
#rgcd=[2, 8, 8]
ans=0
for i in range(N):
if i == 0:
ans = max(ans,rgcd[i])
elif i == N-1:
ans = max(ans,lgcd[i])
else:
ans = max(ans,math.gcd(lgcd[i],rgcd[i]))
print(ans)
ABC124-D - Handstand N people are lined up in a row on the left and right. Given a string S of length N consisting of 0s and 1s and a positive integer K. The i-th person from the left is upright when the i-th letter of S is 0 and upright when it is 1. You give the following instructions up to K times. You don't have to do it even once. Instructions: Choose integers l, r that satisfy 1 ≤ l ≤ r ≤ N. Inverts the l, l + 1, ..., rth states from the left. That is, for i = l, l + 1, ..., r, from the left The i-th person stands upright if he stands upright, and stands upright if he stands upright. Find out how many handstands you can line up in a row with instructions up to K times.
ABC124D.py
N,K = 6 ,2
s = "110010"
nums = []
cnt_1 = 0
cnt_0 = 0
#Run-length compression 10101...Make it into the shape of 1
for i in range(N):
if s[i] == '1':
if cnt_0 != 0:
nums.append(cnt_0)
cnt_0 = 0
cnt_1+=1
else:
if cnt_0 == 0:
nums.append(cnt_1)
cnt_1 = 0
cnt_0 += 1
if i==(N-1):
if cnt_0 == 0:
nums.append(cnt_1)
else:
nums.append(cnt_0)
nums.append(0)
#Cumulative sum
ms = [0]*(len(nums)+1)
for j in range(1,len(nums)+1):
ms[j] = ms[j-1] + nums[j-1]
#ms=[0, 0, 3, 4, 5]
#print(ms)
ans=0
#Organize K so that the for statement works
while (len(ms)-2*K-1)<0:
K-=1
for k in range(0,len(ms)-2*K-1,2):
ans = max(ans,ms[k+2*K+1]-ms[k])
print(ans)
Recommended Posts