Pythonでしゃくとり法（尺取り法）を実装してみる-ABC032

しゃくとり法とは

しゃくとり法は以下のような時に使えるアルゴリズムです。

• 〇〇を満たす区間 (連続する部分列) のうち、最小or最大の長さを求めよ
• 〇〇を満たす区間 (連続する部分列) を数え上げよ

左端と右端のインデックスを条件に合わせて適切に動かすことによって最適化します。

全探索では(O(n^2))かかる問題でもしゃくとり法では(O(n))で計算することが可能です。

では実際に問題を解いていきましょう。

例題

今回は例題としてABC032-Cを扱います。
atcoder.jp

問題文

長さ N の非負整数列 S=s1,s2,...,sN と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1以上の列でないといけません。
・その部分列に含まれる全ての要素の値の積は、K以下である。
もし条件を満たす部分列が一つも存在しないときは、0を出力してください。

実装

この問題ではSという条件を満たす連続する部分列のうち最大のものを求める問題です。

以下の2つの手順を繰り返すことで実装できます。

1. 条件を満たす限り右端を進める
2. 条件を満たさなくなったら左端を条件を満たすまで進める

注意すべき点としては左端と右端が同じ位置に来たときは右端も同時に進めるという処理を忘れないようにしましょう。

n,k = map(int,input().split())
s = [int(input()) for i in range(n)]

if 0 in s:
    print(n)
else:
    r, ans, tmp = 0, 0, 1
    for l in range(n):
        while r < n and tmp*s[r] <= k:
            tmp *= s[r]
            r += 1
        ans = max(ans,r-l)
        if l == r:
            r += 1
        else:
            tmp //= s[l]
    print(ans)

おわりに

問題文の中に「〇〇を満たす区間 (連続する部分列)」という文があった時は尺取り法の可能性を考えてみましょう。

おわり。