内容別リスト/高速化系/尺取法 - 競技プログラミング用 知識集積所

---

雑な説明

要素数nのデータのうち連続する何個かのデータの何か（和、積、種類数など）の中で、条件を満たすものがいくつあるか、または最長区間や最短区間を求める。
通常の方法でやれば計算回数がO(n^2)になるところ、O(n)で済む。

レベル

ABCのC問題以降。

アルゴリズム内容

例えば和が10以下になる区間数を求める場合、以下のようにする。

データ								現在の和	区間数総計	補足
3	1	4	1	5	9	2		0	0	和が10以下なので、現在の長さ0を加える
3	1	4	1	5	9	2		3	1	和が10以下なので、現在の長さ1を加える
3	1	4	1	5	9	2		4	3	和が10以下なので、現在の長さ2を加える
3	1	4	1	5	9	2		8	6	和が10以下なので、現在の長さ3を加える
3	1	4	1	5	9	2		9	10	和が10以下なので、現在の長さ4を加える
3	1	4	1	5	9	2		14	10	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		11	10	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		10	13	和が10以下なので、現在の長さ3を加える
3	1	4	1	5	9	2		19	13	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		15	13	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		14	13	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		9	14	和が10以下なので、現在の長さ1を加える
3	1	4	1	5	9	2		11	14	和が10より大きいので、次は左を進める
3	1	4	1	5	9	2		2	15	和が10以下なので、現在の長さ1を加える 右端がこれ以上右へ行けないので終了

総和以外にも適用できる演算がある。

演算	追加	削除	解説
正数の総和	+	-
正数の総乗	*	/
種類数	++	-- .erase()	mapで内容->個数を管理、0個になったらキー自体を消す。 mapのsize()で種類数を取得できる。

範囲を広げると必ず値が増えるような演算であれば、どんなものでも使える。

また、条件を満たす区間の数以外にも、条件を満たす最長区間、条件を満たさない最小区間、などを求められる。

実装方法は大きく3つある。
以下は、上にある例に対応するコードを3つの異なる方法で書いたものである。
いずれの書き方でも、「範囲が空である場合は、形式的に計算すると条件を満たす」前提で書かれている。
（つまり、空の区間は非合法な区間だが、形式的には合計が0であり10以下という条件を満たしていることを利用している）

• 二重ループ（右側主導）

int limit = 10;
int sum = 0;
int interval_num = 0;

int left = 0;
int right = 0;
while (true) {
  while (sum>limit) {
    sum -= a.at(left);
    left++;
  }
  interval_num += right - left;
  if (right==n) break;
  sum += a.at(right);
  right++;
}

右側カウンタは開区間（つまり、左カウンタ≦i<右カウンタ、という範囲）で考えている。
一見O(n^2)に見えるが、カウンタの進み方が特殊なためO(n)である。

• whileループの中でif分岐（右側主導）

int limit = 10;
int sum = 0;
int interval_num = 0;

int left = 0;
int right = 0;
while (true) {
  if (sum>limit) {
    sum -= a.at(left);
    left++;
  } else {
    interval_num += right - left;
    if (right==n) break;
    sum += a.at(right);
    right++;
  }
}

右側カウンタは開区間（つまり、左カウンタ≦i<右カウンタ、という範囲）で考えている。

• queueを使ってforループ（右側主導）

int limit = 10;
int sum = 0;
int interval_num = 0;

queue<int> que;
for (int i : a) {
  que.emplace(i);
  sum += i;
  while (sum>limit) {
    sum -= que.front();
    que.pop();
  }
  interval_num += que.size();
}

右側カウンタは閉区間（つまり、左カウンタ≦i≦右カウンタ、という範囲）で考えている。
もっとも、コード中にカウンタは登場していないが……。

注意点

右側主導で書いた方が楽。

世の中の尺取法の多くは、左側を1つずつ進めながら「右側をwhileループで伸ばして区間数を処理」をループするという左側主導の方法で紹介される。
しかしその場合、右側のカウンタがうっかり範囲からはみ出る危険性があり、その対処でwhileループの条件がややこしくなりがち。
右側主導で書いた方が単純なコードで済む。

関連アルゴリズム

sliding window法

範囲の左右を両方動かして、条件を満たす範囲を探す目的である点が類似。
こちらのメリットは区間の長さが可変長であること、あちらのメリットは実装が簡単であること。

累積和

一定区間の演算結果を求める点が類似。
こちらのメリットは対応する演算の種類が多いこと、あちらのメリットは後から好きな区間の情報を好きなだけ取れること。
累積和と二分探索（未作成）の組み合わせると、尺取法とほぼ同じことができる場合が多い。
しかし、種類数のように範囲の削減が単純な処理で済まないものは、累積和では対応不可能。
また、O(n*logn)で尺取法よりわずかに遅い。

Fenwick木（未作成）

累積和の上位互換。

segment木（未作成）

Fenwick木の上位互換。