AtCoder Beginner Contest C - Tsundoku Difficulty: 878
This theme, cumulative sum + binary search
At first, I thought it was dynamic programming, but I got TLE ~~ a big loss of time ~~, and switched to binary search.
In input example 1, in each row of the following table, find the maximum number of desks A and B that do not exceed K minutes.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 60 | 90 | 120 | 80 | 150 | 80 | 150 |
| 60 | 90 | 80 | 150 | 80 | 150 | |
| 60 | 80 | 150 | 80 | 150 | ||
| 80 | 150 | 80 | 150 |
Ruby
ruby.rb
n, m, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = Array.new(n + 1, 0)
n.times do |i|
c[i + 1] = c[i] + a[i]
end
d = Array.new(m + 1, 0)
m.times do |i|
d[i + 1] = d[i] + b[i]
end
cnt = 0
0.upto(n) do |i|
break if c[i] > k
e = d.bsearch_index{_1 > k - c[i]}
if e.nil?
cnt = i + m if cnt < i + m
else
cnt = i + e - 1 if cnt < i + e - 1
end
end
puts cnt
ruby.rb
c = Array.new(n + 1, 0)
n.times do |i|
c[i + 1] = c[i] + a[i]
end
d = Array.new(m + 1, 0)
m.times do |i|
d[i + 1] = d[i] + b[i]
end
Cumulative sum.
ruby.rb
e = d.bsearch_index{_1 > k - c[i]}
if e.nil?
cnt = i + m if cnt < i + m
else
cnt = i + e - 1 if cnt < i + e - 1
end
It is a binary search. If the maximum value of the array is exceeded, nil is returned, so that process is included.
Python
python.py
from sys import stdin
import bisect
def main():
input = stdin.readline
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(n):
c[i + 1] = c[i] + a[i]
d = [0] * (m + 1)
for i in range(m):
d[i + 1] = d[i] + b[i]
cnt = 0
for i in range(n + 1):
if c[i] > k:
break
e = bisect.bisect_right(d, k - c[i])
if cnt < i + e - 1:
cnt = i + e - 1
print(cnt)
main()
python.py
e = bisect.bisect_right(d, k - c[i])
if cnt < i + e - 1:
cnt = i + e - 1
It is a binary search. If the maximum value of the array is exceeded, the element number + 1 of the array is returned.
| Ruby | Python | |
|---|---|---|
| Code length(Byte) | 433 | 570 |
| Execution time(ms) | 349 | 246 |
| memory(KB) | 44860 | 47636 |
Referenced site
Recommended Posts