ABC130 D - Enough Array　緑コーダーですが何か？その4

緑のしいだよ。ちきゅうにやさしいよ。

緑コーダーですが何か？第4回目だよ。素数の平方回目とはこりゃまた記念回だね気合い入れていこ

今回の問題はこれ！ ABC130 D - Enough Array

https://atcoder.jp/contests/abc130

連続する整数の総和がある数を超える組み合わせはいくつあるかという問題。

連続する和といったら累積和が定番だけど今回は制約大きいので無理

緑コーダーのわたしならもちろん楽勝だよね（？）

解法

そこで便利なのが尺取り法

ある数を超えるまでキューに追加していき、超えたら先頭から出していくという構造。めっちゃわかりやすいけど、バグが出やすいので注意

dequeだと理解しやすいけど使わなくてもできる。

すごくためになる尺取り法サイト（けんちょんさん）はこっち

https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

速度は落ちるけど二分探索でもできる。

今回は

collections の dequeを使う
dequeを使わず普通のリストだけでやってみる。
二分探索

ちなみにdequeの先頭の要素取り出す操作はO(1) だから速度は一緒だよ

すごくためになるサイトはこっち

https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

実装1

    from collections import deque
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    q = deque()
    s = 0
    ans = 0
    for e,i in enumerate(A):
        q.append(i)
        s+=i
        while s>=K:
            t = q.popleft()
            s-=t
            ans+=N-e
    print(ans)

実装2

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    q = []
    s = 0
    ans = 0
    c = 0
    for e,i in enumerate(A):
        q.append(i)
        s+=i
        while s>=K:
            s-=q[c]
            ans+=N-e
            c+=1
    print(ans)

解放（二分探索）

二分探索を使った方法ではまず累積和をもとめる。そのあと累積和の(それぞれの要素-K)をした上で二分探索し境界線を探す

実装3(right)

    import bisect
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]
    for i in A:
        S.append(S[-1]+i)
    ans = 0
    for i in S:
        ans += bisect.bisect_right(S,i-K)
    print(ans)

実装3(left)

    import bisect
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]
    for i in A:
        S.append(S[-1]+i)
    ans = 0
    for i in S:
        ans += N-bisect.bisect_left(S,i+K)+1
    print(ans)

あとがき

これも昔の汚い提出出てきた。。このとき初めて尺取り法を知ってかんどうしたんだっけ

https://atcoder.jp/contests/abc130/submissions/6840176