しゃくとり法

しゃくとり法

しゃくとり法 というアルゴリズムを使って、下記の問題を解いてみます。

[問題]

1
2
3
長さ<b>n</b>の数列 <b>a1,a2,..</b> と整数<b>S</b>が与えられます。
連続する部分列で、その合計が<b>S</b>以上となるもののうち、<b>最小の長さ</b> を求めなさい。
解が存在しない場合は<b>0</b>を出力しなさい。

[条件]

1
2
3
・長さ<b>n</b>は <b>5以上 100000未満</b>
・数列の各要素は、<b>0より大きく10000以下</b>
・整数Sは <b>100000000未満</b>

この問題は、区間の先頭と末尾を 交互 に進めながら条件を満たす 最小の区間 を調べることで解くことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a = [5,1,3,5,10,7,4,9,2,8]
S = 15

n = len(a)        # 配列数
res = n + 1       # 最小区間の初期値（配列数＋１）
s = 0             # 集計開始位置
t = 0             # 集計最終位置
total = 0         # 合計値

while True:
    while t < n and total < S:  # 集計最終位置が配列内かどうか、合計値がSより小さいかどうか
        total += a[t]           # 合計値を算出
        t += 1                  # 集計最終位置を１つうしろにずらす
    if total < S:
        break                   # 合計値が条件(整数S以上)に達していないので終了（集計最終位置が配列を超えた）
    res = min(res, t - s)       # 合計値が条件を満たしている部分列の長さが、より短い場合は更新
    total -= a[s]               # 合計値から先頭の要素をひく
    s -= 1                      # 集計開始位置を１つうしろにずらす

if res > n:       # 配列数より大きいので解がなかった
    res = 0       # 解がなかったため0を設定
print(res)        # 解を出力

[実行結果]

1
2

配列の４番目から５番目の２要素(5,10)を足すと15を超えますので、出力結果の2は正解ということになります。