しゃくとり法を復習してみた(Python)

はじめに

• しゃくとり法について復習してみました

アルゴリズム概要

• しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
• 英語でいうとtwo pointersらしい
• O(n²) をO(n)にするテクニックの1つであるしゃくとり法
• 「連続する部分列」で使う
  • 「条件」を満たす区間 (連続する部分列) のうち、最小の長さを求めよ
  • 「条件」を満たす区間 (連続する部分列) のうち、最大の長さを求めよ
  • 「条件」を満たす区間 (連続する部分列) を数え上げよ
• 愚直に全探索をしようと思うと、n(n+1)/2n個の区間がある (後述) ため O(n²)の計算量を要します。それを鮮やかに O(n)に改善します。
• 実装イメージ
  • i(left)はfor文で最初から最後まで動かしていく
  • j(right)はwhile文で条件を満たす限り動かしていく
    • ポイントは、iをすすめるときに、jを初期化（i+1などに）しない。jはそのまま進めていく（ここで計算量を減らす）
    • = 単純に考えれば、right = left, left+1, left+2, ..., と調べて行って、条件を満たさなくなる場所を検出することで実現できるが、
    • ->left を固定して right を右に動かして、今度は left を 1 増やして...」という動きをさせる。この動きがしゃくとり虫のようなので、しゃくとり法と呼ばれます。

問題

AOJ Course The Number of Windows

解法

n,x = map(int,input().split())
a = list(map(int,input().split()))

ans = 0
tmp = 0
right = 0

for left in range(n):
    while right < n and tmp + a[right] <= x:
        tmp += a[right]
        right += 1
    ans += right - left

    if right == left:
        right += 1
    else:
    tmp -= a[left]

print(ans,count)

POJ 3061 Subsequence

ポイント

• left によっては条件を満たす right が存在しなくなってしまう (上の表の ∞) ので、その判定を怠らないようにします

解法

n,x = map(int,input().split())
a = list(map(int,input().split()))

right = 0
tmp = 0
ans = 10**9+7

for left in range(n):
    while right < n and tmp < x:
        tmp += a[right]
        right += 1

    # これ以上 left を進めてもダメなので、for文を打ち切る（右端まで行ってダメだったので）
    if tmp < x:
        break

    ans = min(ans,right - left)

    if right == left:
        right += 1
    else:
        tmp -= a[left]

print(ans)