AtCoder Beginner Contest D - Enough Array Difficulty: 859
This theme, cumulative sum + binary search
Problem statement (Condition) The sum of the values of all the elements contained in the continuous subsequence is K or more. You can see from that the cumulative sum is used, but since 1 ≤ N ≤ 100_000, if you turn the loop twice, it becomes TLE.
Therefore, since the cumulative sum is a monotonous increase, a binary search is also used to reduce the amount of calculation.
Ruby
ruby.rb
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
acc = 0
x = [0] + a.map{|v| acc += v}
cnt = 0
x.each do |y|
j = x.bsearch_index{|z| z - y >= k}
if j == nil
break
else
cnt += n - j + 1
end
end
puts cnt
accumulate.rb
acc = 0
x = [0] + a.map{|v| acc += v}
The cumulative sum is calculated here. ** Addition ** I modified it to the code you received in the comments.
bsearch.rb
j = x.bsearch_index{|z| z - y >= k}
Although it is a binary search, lower_bound in *** C ++ *** becomes bsearch or bsearch_index in *** Ruby ***.
Python
python.py
from sys import stdin
def main():
import bisect
import itertools
input = stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = [0] + list(itertools.accumulate(a))
cnt = 0
for z in x:
j = bisect.bisect_left(x, k + z)
if j <= n:
cnt += n - j + 1
print(cnt)
main()
accumulate.py
x = [0] + list(itertools.accumulate(a))
*** Python *** has a function called ʻaccumulate` that finds the cumulative sum.
bisect.py
j = bisect.bisect_left(x, k + z)
It is a binary search, but use bisect or bisect_left bisect_right.
If the array contains a number to search for, bisect returns the position to the right of that number and bisect_left returns the position to the left.
for.py
for z in x:
for i in range(n):
When I turned the loop with range (), it was TLE.
| Ruby | Python | |
|---|---|---|
| Code length(Byte) | 238 | 377 |
| Execution time(ms) | 165 | 101 |
| memory(KB) | 11780 | 14196 |
Referenced site
Recommended Posts