尺取り法を5分で理解するためのノートを書く。

しゃくとり法が有効な場面

長さnの数列aにおいて、

とある条件を満たす区間(連続する部分列)のうち、最小のxxを求めよ とある条件を満たす区間(連続する部分列)のうち、最大のxxを求めよ とある条件を満たす区間(連続する部分列)のうち、xxを満たすものを数えよ

のような、条件を満たす区間がいくつかあって、そのうちxなものを求めよという場合に有効になる。

考え方と計算量

しゃくとり法が有効な場面において、愚直パターンと比較した計算量を考える。この時の計算量は数列aの長さnに比例する。

イメージはそれぞれ次のようになる。

愚直パターンの場合は**まず最初に部分列の組み合わせを全て洗い出し、その部分列が条件を満たすか？**という方針になる。

このときの部分列の作り方は数列の要素間のどこに仕切りを入れるか？だ。仕切りを入れた結果できる区間の数はn(n+1)/2より計算量はO(n2)となる。

一方でしゃくとり法は、左または右を固定し、部分列の条件を満たす範囲を探しながら左から右まで仕切りを動かすという方針になる。

この時の部分列の作り方は、右から左まで(=n)の範囲で仕切りの位置をずらしていくだけなので、計算量はO(n)となる。

だいたいイメージが湧いたところで、実際の例題を踏まえて実装パターンを確認する。

例題: ABC032 C

C - 列

この問題を要約すると長さnの数列sがあり、連続する部分列の積がk以下のもののうち最も長いものを求めよとなる。しゃくとり法を使ってくださいと言ってるような問題だ。

僕は以下のように実装した。

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

# このforは問題固有の実装のため無視して良い
for num in s:
  if num == 0:
    print(n)
    exit()

right=0
ans=0
res=1
for left in range(n):
  # ここが部分列の条件
  while right<n and res*s[right]<=k:
    res*=s[right]
    right+=1
  ans=max(right-left, ans)
  if left==right:
    right+=1
  else:
    res//=s[left]
print(ans)

外側のforは左の仕切り、中のwhileは右の仕切りの移動を表している。ポイントは左と右が重なる場面で、このタイミングでは右を一つずらす。それ以外の場合は、一つ前の左の範囲がずれる。なので、前の範囲の計算を除いてやる必要がある。

この形がしゃくとり法の基本形になる。あとは条件によって判定だけ変えてあげるだけでよい。