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)
の組み合わせを探索することができる。