演習課題「しゃくとり法の実装」
整数n,kと長さnの配列aが与えられます。
この配列の中で、総和がk未満の区間の個数を求めてください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。
期待する出力値
4
＃08:しゃくとり法
このチャプターでは、しゃくとり法について学習します。
しゃくとり法を適用するための条件には、いくつかの制約があります。これらの制約を満たしていれば、必ずしゃくとり法を適用することができます。
・ある区間が条件を満たすなら、その区間に含まれるすべての区間が条件を満たす
・ある区間が条件を満たさないなら、その区間を含むすべての区間が条件を満たさない
・左端や右端を1つ動かしたとき、条件を満たすかどうかの判定を高速に行うことができる
しゃくとり法のl,rが表す区間は、半開区間[l,r)になります。
条件判定にかかる時間計算量がO(x)のとき、しゃくとり法の全体での時間計算量は、O(nx)となります。
これは、ループに必要な回数がnであり、また右端を伸ばす回数の合計もnであることによります。
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
# 現在の右端を表す変数r,現在の総和を表す変数sum_value,答えを表す変数countを0で初期化
r, sum_value, count = 0, 0, 0
# 左端lを0からn-1まで繰り返す
for l in range(n):
# rがnより小さく、sum_valueにa[r]を加えてもkを超えない間
while r < n and sum_value+a[r] <= k:
# sum_valueにa[r]を加えて右端rを1ずつ増やす
sum_value += a[r]
r += 1
# r-lをcountに加える
count += r - l
# もしlがrと同じなら
if l == r:
# rを1増やす
r += 1
# そうでなければ
else:
# sum_valueからa[l]を引く
sum_value -= a[l]
# countを出力
print(count)
5 2
1 1 2 2 2