尺取り法

はじめに

個人的に苦手意識の強かった尺取り法について、弱点を補うべく最近勉強しました。主に添字の管理で混乱してしまうことが多かったので、めぐる式二分探索のようなテンプレ（型）を作ることを目標にしました。自分なりにまとめてみましたが、間違いがあったらすみません。

尺取り法とは

尺取り法とは配列の中から特定の条件を満たす連続部分列の数を数える場合などに使われるテクニックです。連続部分列の範囲を [L, R] で表したとき、L と R の動かし方が尺取り虫のようなのでこのように呼ばれます。

高速化の仕組み

全探索に比べて小さな計算量で配列全体を調べることができます。具体的には以下の通りです。上が全探索、下が尺取り法です。

全探索の場合は L <= R の条件を設定した場合でも N * (N-1) / 2 、つまり O(N^2) かかります。尺取り法は L, R を 1 から N まで動かすだけでいいので O(N) で済みます。

2つの図を見比べると、尺取り法ではそれぞれの L に対して R を途中までしか調べていません。それ以上大きな R を調べても条件を満たさないことが明らかなため、調べても無駄だからです。言い換えると配列全体が「これ以上調べても無駄」とわかる構造になっていることが尺取り法が使える条件です。

尺取り法が使える条件

「これ以上調べても無駄」というのは、例えば「ある狭い区間（空の配列 [] など）では条件を満たし、そこから区間を拡げていくとどこかで条件を満たさなくなり、それ以後ずっと条件を満たさない」といった場合です。「ある広い区間が条件を満たしているのなら、それより狭い区間も条件を満たす」と言い換えることもできます。条件を満たす／満たさないを逆にしても構いません。条件を満たす区間と満たさない区間がはっきりと分かれている必要があるわけですね。

ABC247-Eを例にとって見てみます。いきなりE問題を出したのは、この問題が僕が尺取り法の適用条件について考えるきっかけを作ってくれたからです。

これはそのままの配列だと尺取り法が使えないので使える形に加工してから尺取り法を使うという問題です。例えば

N, X, Y = 10, 4, 2
A = [4, 3, 2, 5, 2, 4, 3, 1, 2, 3]

の場合を考えます。配列 A を左から見ていくと

• [4] : 最大値4 最小値4 条件を満たさない
• [4, 3] : 最大値4 最小値3 条件を満たさない
• [4, 3, 2] : 最大値4 最小値2 条件を満たす
• [4, 3, 2, 5] : 最大値5 最小値2 条件を満たさない

以後ずっと条件を満たしません。これは「満たさない → 満たす → 満たさない」とコロコロ変わるので駄目です。そこで X より大きな数と Y より小さな数で配列 A を区切って分けることで Y 以上 X 以下しか存在しない配列を用意し、尺取り法を使えるようにしようというのがこの問題の趣旨です。

区切った後の配列は [4, 3, 2], [2, 4, 3], [2, 3] となり、いずれも条件を「満たさない → 満たす」と一度しか変化しない、もしくはずっと満たさないので尺取り法を使うことができます。

尺取り法の動き

これを踏まえてもう一度先ほどの図を見てみましょう。今、「狭い区間では条件を満たし、拡げていくとどこかで条件を満たさなくなる」場合を考えます（さっきのABC247-Eとは逆です）。

実装

今度は ABC032-Cを見てみます。
https://atcoder.jp/contests/abc032/tasks/abc032_c

数列に 0 が含まれる場合は長さ N が答えになってしまうので場合分けして処理し、それ以外の場合について尺取り法を使います。

なお区間を表現する際に使う L, R ですが、ここでは配列の添字ではなくその間の区切りを指すことにします。1-index で考えます。

つまり (L, R) = (1, 1) なら部分列は空で、(L, R) = (1, 2) なら [1]、(L, R) = (1, 3) なら [1, 2] となります。半開区間 [L, R) ともいいます。L の側は添字 L も区間に含み、R の側は添字 R は区間に含みません。

ans = 0
R = 1
value = 1 # [条件判定用変数の初期化]
for L in range(1, N+1): 
  while (R <= N and value * A[R] <= K): # [Rを用いた条件判定式]
    value *= A[R] # [R を用いて条件判定用変数の値を変える]
    R += 1

  ans = max(ans, R - L) # [この問題の答えを数える部分]

  if L == R:
    # L が R に追いついた場合の処理。
    # このとき区間 [L, R) は空になっているので value は既に 1 になっているため、
    # value //= A[L] を実行する必要はない
    R += 1
  else:
    value //= A[L] # [L を用いて条件判定用変数の値を変える]
    
print(ans)

テンプレ

これがテンプレです。灰色の四角のところを書き換えて使います。アレンジが必要な問題も出てきますが、L と R を動かす手順はこれでいいと思います。

実際に解いてみる

ABC038-C

• 条件判定用の変数とそれの書き換えは必要ありません。
• R を用いた条件判定式に単調増加かどうかをチェックする式を入れます。
• 答えを数える部分にしかるべき式を入れます。

N = int(input())
A = [10**6] + list(map(int, input().split())) # A[0] を大きくして答えに混ざらないようにする
ans = 0
R = 1
for L in range(1, N+1): 
  while (R <= N and A[R-1] < A[R]):
    R += 1
  ans += R - L + 1
  if L == R:
    R += 1  
print(ans)

ABC098-D

• 条件判定用の変数として xor, sum の計算結果を入れる変数を用意しておきます。
• R を用いた条件判定式を用意します。
• 条件判定用の変数を書き換えます。R の方は簡単です。L の方は xor が厄介ですが、xor には同じものをぶつければ打ち消せるのでそのまま xor を掛けます。
• 答えを数える部分にしかるべき式を入れます。

N = int(input())
A = [0] + list(map(int, input().split()))
ans = 0
R = 1
part_xor, part_sum = 0, 0
for L in range(1, N+1): 
  while (R <= N and part_xor ^ A[R] == part_sum + A[R]):
    part_xor ^= A[R]
    part_sum += A[R]
    R += 1
  ans += R - L
  if L == R:
    R += 1
  else:
    part_xor ^= A[L]
    part_sum -= A[L]  
print(ans)

ARC022-B

• 条件判定用の変数として何の味が何個あるかを表す配列を用意します。
• R を用いた条件判定式として、A[R] の味が既にあるかどうか調べる式を用意します。
• 条件判定用の変数を書き換える処理を行います。1足す、1引くだけでOKです。
• 答えを数える部分にしかるべき式を入れます。

N = int(input())
A = [0] + list(map(int, input().split()))
ans = 0
R = 1
part_taste_list = [0 for _ in range(10**5 + 1)]
for L in range(1, N+1): 
  while (R <= N and part_taste_list[A[R]] == 0):
    part_taste_list[A[R]] += 1
    R += 1
  ans = max(ans, R - L)
  if L == R:
    R += 1
  else:
    part_taste_list[A[L]] -= 1  
print(ans)

ABC130-D

• 条件判定用の変数として合計値を格納する数字を用意します。
• R を用いた条件判定式として A[R] を足してみる式を用意します。
• 条件判定用の変数を書き換える処理を行います。A[R]を足す、A[L]を引くだけでOKです。
• 答えを数える部分にしかるべき式を入れます。

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
# K 未満のときを探して余事象を考える。
ans = 0
R = 1
sum_value = 0
for L in range(1, N+1): 
  while (R <= N and sum_value + A[R] < K):
    sum_value += A[R]
    R += 1
  ans += R - L
  if L == R:
    R += 1
  else:
    sum_value -= A[L]  
print(N * (N+1) // 2 - ans)

ABC369-C

今回は特殊です。長さ1または2の数列は必ず等差数列になるので、R が常に L+2 以上になるようにします。

• LがRを追い越すかどうかの判定は今回は必要ありません。
• 条件判定用の変数とそれの書き換えは必要ありません。
• R を用いた条件判定式には等差数列になっているかどうかの判定を書きます。
• 答えを数える部分にしかるべき式を入れます。

N = int(input())
A = [10**9+1] + list(map(int, input().split()))
ans = 0
R = 1
for L in range(1, N): 
  R = max(R, L+2) # 強制的に L の 2 つ先から始める
  while (R <= N and (A[R]-A[R-1] == A[R-1]-A[R-2])):
    R += 1
  ans += R - L
ans += 1 # L = N のとき、配列が [A[N]] となってこのときに 1 つだけ成り立つので加える
print(ans)

ABC229-D

• 条件判定用の変数として残りの操作可能な回数を持っておきます。
• R を用いた条件判定式において残りの操作可能な回数を見るようにします。
• 条件判定用変数の書き換えをします。操作可能な回数が減ったり戻ったりします。
• 答えを数える部分にしかるべき式を入れます。

S = "-" + input()
K = int(input())
N = len(S) - 1
ans = 0
R = 1
remain = K
for L in range(1, N+1): 
  while (R <= N and ((remain >= 1 and S[R] == ".") or S[R] == "X")):
    if S[R] == ".":
      remain -= 1
    R += 1
  ans = max(ans, R - L)
  if L == R:
    R += 1
  else:
    if S[L] == ".":
      remain += 1   
print(ans)

ABC384-D

周期性を利用します。 S ではなく S を sum(A) で割った余り amari を使います。また、循環する問題への対応として数列 A を 2 つ繋げた配列を用意しておきます。これに伴い配列の長さがいつもの N から 2 * N になるので注意してください（僕はこれを忘れて 1 ペナルティを食らいました）。

• 条件判定用の変数として合計値を格納する数字を用意します。
• R を用いた条件判定式として、amari 以下であるかどうかを調べる式を書きます。
• 条件判定用変数の書き換えをします。足したり引いたりするだけです。
• 答えを判定する部分では合計値が amari に一致しているかどうかを調べています。

N, S = map(int, input().split())
A = list(map(int, input().split()))
AA = [0] + A + A
amari = S % sum(A)
if amari == 0:
  ans = "Yes"
else:
  ans = "No"

R = 1
sum = 0
for L in range(1, 2*N+1): 
  while (R <= 2 * N and sum + AA[R] <= amari):
    sum += AA[R]
    R += 1
  if sum == amari:
    ans = "Yes"
  if L == R:
    R += 1
  else:
    sum -= AA[L]  
print(ans)

ちなみにこの問題はコンテスト本番で解きましたが、焦っていたこともあって変な解き方になりました。先に累積和を計算しておき AA[R] - AA[L] == amari となる L, R の組があるかどうかを調べるのが本来の解法だと思います。しかしテンプレのおかげで尺取り法自体は問題なく動作しました。焦っていても道具としてテンプレを使いこなせており、しかも有効に使えていることがわかります。

終わりに

2024年11月のABC381に参加した際、D問題が解けませんでした。尺取り法っぽいと思いつつ苦手意識があったのでそれを避けて解こうとし、結局駄目でした。これではいけないと思い今一度尺取り法を勉強し直そうと思い始めました。そこで前述のABC247-Eに出会い、尺取り法が使える条件について真剣に考えるきっかけになりました。今まではなんとなく雰囲気だけで尺取り法っぽいものを使っていたことがわかりました。

勉強した矢先にABC384-Dで尺取り法が使える機会がやってきました。当然尺取り法を使い、テンプレのおかげで短時間で正解に辿り着くことができました。おかげでレートも上がり936まで来ました。色変までは果てしなく遠いですが少しでもレートが上がっているのは勉強の励みになります。

このテンプレが通用しない問題、ABC369-Cのようにアレンジしないと使えない問題も出てくるとは思いますが少なくとも L, R の動かし方はこれでいいのではないかと思います。これまでは添字のズレに悩まされていました。while ループの中で R が進みすぎたのでループを出てから -1 するなどということもやったことがあります。今回の勉強によりこのような悩みから解放され、臆することなく尺取り法を使えるようになったのはとても嬉しいことです。