[AtCoder]ABC130 D-Enough Array

AtCoder

2021.11.122021.10.06

【問題】

D - Enough Array

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

【方針】累積和を考える。numpyを用いてもいいが、

import itertools
itertools.accumulate(list)

が簡単。累積和を考えると、ある一定以上の項からは\(k\)以上となる（ならない場合もあるが）。それをまず

import bisect as bi
answer = n-bi.bisect_left(b, k)

として足しておく。後は、初項から順に見ていき、初めて和が\(k\)以下になってしまう項を求める。これも順に見ていかなくても、bisectで探すのが楽。

【解答】

#input
n, k = map(int, input().split())
a = list(map(int, input().split()))

#output
import itertools
import bisect as bi
b = list(itertools.accumulate(a))
#cumsumである一定以上の項からkを超えるとする。
#[a_1, a_2, ..., k+x, ..., ]
#xより小さい項は引ける。
c = bi.bisect_left(b, k)
answer = n-c

for i in range(c, n):
    answer += bi.bisect_right(b, b[i]-k)
        
print(answer)

【提出結果】