ABC130D - Enough Array

ABC

ABC130D問題文

問題概要

ある和以上の連続部分列の個数を求める問題

考え方

条件を満たす連続部分列の何かを求める系の問題には、しゃくとり法を思い浮かべる.

調べていたら、累積和+二分探索の考え方もありました

コード

しゃくとり法 O(N)

for でleftを動かして, その中のwhileでrightを動かしていく. whileの条件にrightが右に進む条件をandでまとめるといいように思いました.

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
right = 0
part_sum, ans = 0, 0
for left in range(n):
    while part_sum < k and right < n: # rightが右に進む条件をandでここにまとめる
        part_sum += a[right]
        right += 1
    # rightが数列の右端まで行ってwhileを通らなかったり、抜ける場合があるためにこれを設ける
    if part_sum >= k:
        ans += n-(right-1)
    part_sum -= a[left] # leftが次のループでインクリメントするのでその分を引く
print(ans)

累積和+二分探索 O(NlogN)

このやり方好きですw

from bisect import bisect_right
n, k = map(int, input().split())
a = tuple(map(int, input().split()))
ans = 0
acc = [0]
# 累積和作成
for i in range(n):
    acc.append(acc[-1]+a[i])
for part in acc:
    if part < k:
        continue
    ans += bisect_right(acc, part-k)
print(ans)

考え方として、ABC172C - Tsundokuがとても似ていると思いました.

この問題最初解いた時、貪欲でやってしまって大失敗した苦い思い出...