Learn cumulative sum in Python

What is cumulative sum?

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

  1. Prepare a cumulative sum table and store the cumulative sum->
  2. Prepare a total value table and store the section total from the cumulative sum table->
  3. Sum in the total value table is the solution However, this time the sum of mt [i] -mt i-K is the 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

Learn cumulative sum in Python
[Python] Cumulative sum ABC186D
Implement sum in Python
[Python] Cumulative sum ABC179D
Learn exploration in Python # 1 Full exploration
Quadtree in Python --2
Python in optimization
Learn the design pattern "Prototype" in Python
CURL in python
Learn the design pattern "Builder" in Python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Cumulative sum commentary
Meta-analysis in Python
Learn the design pattern "Flyweight" in Python
Learn the design pattern "Observer" in Python
Learn the design pattern "Memento" in Python
Unittest in python
Learn the design pattern "Proxy" in Python
Learn the design pattern "Command" in Python
Epoch in Python
Learn the design pattern "Visitor" in Python
Sudoku in Python
Learn the design pattern "Bridge" in Python
DCI in Python
Learn the design pattern "Mediator" in Python
quicksort in python
Learn the design pattern "Decorator" in Python
nCr in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Learn the design pattern "Iterator" in Python
Lifegame in Python.
FizzBuzz in Python
Project Euler # 16 "Sum of Powers" in Python
Sqlite in python
StepAIC in Python
Learn the design pattern "Strategy" in Python
N-gram in python
LINE-Bot [0] in Python
Learn the design pattern "Composite" in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
Learn the design pattern "State" in Python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Learn the design pattern "Adapter" in Python
Quad-tree in Python
Learn dynamic programming in Python (A ~ E)
Reflection in Python
Chemistry in Python