Pythonで理解する蟻本「3-2 Subsequence（POJ No.3061）」(p.135)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-2 Subsequence（POJ No.3061）」(p.135)
のコードをPythonで書き直したものとなっています。

入力

入力例1

10 15
5 1 3 5 10 7 4 9 2 8

入力例2

5 11
1 2 3 4 5

二分探索を用いた解答（O(n log n)）

import sys
from bisect import bisect_left

# 入力
n, S = map(int,input().split())
a = list(map(int,input().split()))

SUM = [0] * (n + 1)

# SUMを計算する
for i in range(n):
    SUM[i + 1] = SUM[i] + a[i]

if SUM[n] < S:
    # 解が存在しない
    print(0)
    sys.exit()

res = n
s = 0
while SUM[s] + S <= SUM[n]:
    # 終端tを二分探索で求める
    t = bisect_left(SUM, SUM[s] + S)
    res = min(res, t - s)
    s += 1

print(res)

しゃくとり法を用いた解答（O(n)）

# 入力
n, S = map(int,input().split())
a = list(map(int,input().split()))

res = n + 1
s = 0
t = 0
SUM = 0

while True:
    while t < n and SUM < S:
        SUM += a[t]
        t += 1
    if SUM < S:
        break
    res = min(res, t - s)
    SUM -= a[s]
    s += 1

if res > n:
    # 解が存在しない
    res = 0
print(res)