AOJ DSL_3_C The Number of Windows

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_C&lang=ja

回答

import sys
import os

il = lambda: list(map(int, sys.stdin.buffer.readline().split()))

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    A = il()
    Q = il()

    for q in Q:
        # 合計, 範囲, 左端の初期化
        sm, ret, l = 0, 0, 0
        for r in range(N):
            # 右端を0から、合計がq以下になる
            # 最大位置まで進める
            sm += A[r]
            while sm > q:
                # 合計がqを上回る場合、
                # 左端をインクリメント
                sm -= A[l]
                l += 1

            # 合計がq以下となる範囲
            ret += r - l + 1

        print(ret)


if __name__ == '__main__':
    main()

考え方

尺取り法を用いて、条件に合う範囲の探索を行なう。
尺取り法については下記を参考にした。

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

長さNの数列A(A1, A2, ... ,An)に対して、
左端(l)から右端(r)までの区間の合計を求める。

合計の値が整数qを上回るまで右端(r)を進めて、
進めることが出来た範囲が、左端(l)のある特定の位置で条件を満たす整数の組となる。
また、合計の値が整数qを上回った場合、
合計の値が整数qを下回るまで、左端(l)をインクリメントする。
左端(l)を進めることによって、再度右端(r)を進めることができるため、
全ての条件を満たす整数(l, r)の組み合わせを探索することができる。