ABC172-C_Tsundokuをpythonで解いた（累積和+二分探索or尺取り法）

問題

• ABC172-C_Tsundoku

問題概要

• 机が二つ。それぞれに本が積まれている。上から順に読んでいく。k分を超えない範囲で、何冊読めるか。

解法(1)

ポイント

• 2つの変数の和の（条件下での）最大値を探す
  • -> 一つを固定して、二分探索 or 尺取り法
  • <- 単調増加であることが大事

• 累積和

配列aに対して累積和sを求めると、配列aの区間[left, right]の総和が
s[right] - s[left]
でO(1)で求められる

from itertools import accumulate
a_list = list(map(int, input().split()))
# -> [60, 90, 120]

sum_a_list = list(accumulate([0] + a_list))
# -> [0, 60, 150, 270]

• 二分探索

import bisect

example_list = [1,3,4,5,6,7,9,10,13,16,18,22,24,25,26] 
target = 22

example_list = sorted(example_list)

target_index = bisect.bisect_left(example_list,target)

print(target_index)

コード

n,m,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

from itertools import accumulate
import bisect

sum_a_list = list(accumulate([0] + a_list))
sum_b_list = list(accumulate([0] + b_list))

ans = 0
b_idx = 0
for a_idx in range(n+1):
    if sum_a_list[a_idx] > k:
        continue

    time_rest = k - sum_a_list[a_idx]
    # 同じ数字を取った場合を考慮してleftでなくright
    b_idx = bisect.bisect_right(sum_b_list,time_rest) - 1

    ans = max(ans, a_idx + b_idx)

print(ans)

解法(2)

ポイント

• 尺取り法
  • しゃくとり法を復習してみた(Python)
  • 単調増加であることを利用して、「インデックスを下げ続ける（初期化しない）」ことが計算量を削減するポイント

* 実装イメージ
  * i(left)はfor文で最初から最後まで動かしていく
  * j(right)はwhile文で条件を満たす限り動かしていく
    * ポイントは、iをすすめるときに、jを初期化（i+1などに）しない。jはそのまま進めていく（ここで計算量を減らす）
    * = 単純に考えれば、right = left, left+1, left+2, ..., と調べて行って、条件を満たさなくなる場所を検出することで実現できるが、
    * ->left を固定して right を右に動かして、今度は left を 1 増やして...」という動きをさせる。この動きがしゃくとり虫のようなので、しゃくとり法と呼ばれます。

コード

n,m,k = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

from itertools import accumulate
sum_a_list = list(accumulate([0] + a_list))
sum_b_list = list(accumulate([0] + b_list))

ans = 0
b_idx = m
for a_idx in range(n+1):
    if sum_a_list[a_idx] > k:
        continue

    while sum_a_list[a_idx] + sum_b_list[b_idx] > k:
        b_idx -= 1

    ans = max(ans, a_idx + b_idx)

print(ans)