尺取り法備忘録

尺取り法、してますか？

条件を満たす列に対して

• 条件を満たす連続部分列の最大/最小長さ
• 条件を満たす連続部分列の数え上げ

などを求めるアルゴリズムとして、尺取り法が知られています。 要求される条件は、大まかには以下のどちらかです。

• ある区間$I$が条件を満たすならば、$\forall i \subseteq I$もまた条件を満たす。
• ある区間$I$が条件を満たすならば、$\forall i \supseteq I$もまた条件を満たす。

けんちょんさんの記事によると、これらの条件は次のようにも言い換えられます。

• 区間の最左のインデックスを$l$、条件を満たす区間の右のインデックス最大値を$f(l)$としたとき、$f(l)$は広義単調増加。
• 区間の最左のインデックスを$l$，条件を満たす区間の右のインデックス最小値を$f(l)$としたとき、$f(l)$は広義単調増加。

いきなり抽象的なことを言ってもしょうがないので、具体例を見ていきましょう。

例題 : AOJ DSL_3_C (The Number of Windows)

問題

長さ$N$の数列$a_1, a_2, a_3, \dots , a_N$が与えられる。次の$Q$個の質問に答えよ。

整数$x_i$が与えられる。$1 \leq l \leq r \leq N$かつ$\sum_{i=l}^{r} \leq x_i$を満たす$(l, r)$の組の個数を求めよ。

制約

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 500$
• $1 \leq a_i \leq 10^9$
• $1 \leq x_i \leq 10^{14}$

$1 \leq a_i$であるため、$\sum_{i=l}^{r} a_i \leq x_i$が成立するなら、これよりも狭い区間の和もまた$x_i$以下になります。 すなわち、尺取り法の条件を満たしています。

この問題は、ざっくり次のようなアルゴリズムで解くことができます。(わかりやすさのため、一部正確でないです)

1. $l = 0, r = 0, \mathrm{ans} = 0$とする。
2. 総和が$x_i$を超えないギリギリまで$r$を右にずらしていく
3. $\mathrm{ans}$に$r-l$を加算する
4. $r$の位置はそのままにして、$l$を一つ右にずらす
5. 手順2に戻る

このアルゴリズムは、すべての始点に対してギリギリ和が$x_i$を超えない右端を求めていると捉えることができます。 ここで大事なのは手順4です。尺取り法の条件は、つまるところ手順4をして良いかどうか？ということになります。

なぜ手順4をしてよいかと言うと、手順3が終わった時点での$\sum_{i=l}^{r} a_i$が$x_i$を超えないため、当然それよりも狭い範囲を指す$[l+1, r]$の総和も$x_i$を超えないからです。

この工夫を行うことによって、$l, r$ともに$O(N)$回の移動でアルゴリズムが終了し、全体$O(N)$になります。

さて、ここまでは概要をざっくり説明してきました。 ここからは実装の詳細を説明します。

まず、区間を$l, r$を用いて表すわけですが、これは右半開区間$[l, r)$を用いましょう。 これは空である区間を自然に表現できるからです。両端閉区間だと面倒になります。

具体例を挙げます。上の問題で、$a = (1, 5, 10)$かつ$x_1 = 7$だったとします。 このとき、条件を満たす連続部分列は次のようになります。(0-indexed)

$(0)$, $(0, 1)$, $(1)$

このように、左端が$2$になるような連続部分列で条件を満たすようなものは存在しません。すなわち空な区間が出てきてしまいます。 これは右半開区間なら$[2, 2)$と表現できますが、閉区間だときれいに表現できなくなり、場合分けが増えます。

さて、実装しましょう。以下の実装では次のようなものが上の方にあると仮定してください。

using namespace std;
using ll = long long;

int N, Q; cin >> N >> Q;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];

まずは左端に関するループですから、それを作ります。 それと、現在の総和を保持する変数が必要です。

// クエリ入力
ll x; cin >> x;

int l = 0, r = 0;
ll sum = 0;

while (l < N) {
    l++;
}

forでもいいですが、個人的にはwhile推しです。 初期状態で$[0, 0)$の空区間を示していることに注意してください。 このとき総和が$0$なので、整合性が取れています。

限界まで右に伸ばします。

// クエリ入力
ll x; cin >> x;

int l = 0, r = 0;
ll sum = 0;

while (l < N) {

    // 右に伸ばす
    while (r < N) {
        if (x < sum + A[r]) break;
        sum += A[r];
        r++;
    }

    l++;
}

右は開区間なので、A[r]はまだ含まれていない要素ということなります。これを足してもxを超えなければ足し、超えるならbreakします。 また、そもそもrは上限があるので、それもwhileの条件に入れています。

答えを加算します。

// クエリ入力
ll x; cin >> x;

int l = 0, r = 0;
ll sum = 0;

while (l < N) {

    // 右に伸ばす
    while (r < N) {
        if (x < sum + A[r]) break;
        sum += A[r];
        r++;
    }

    // 答えを加算
    ans += r - l;

    l++;
}

区間の左側が$l$であるとき、右側として$[l, r)$のどこからとっても条件を満たします。なので、r - lを足します。

左側を進めます。

// クエリ入力
ll x; cin >> x;

int l = 0, r = 0;
ll sum = 0;

while (l < N) {

    // 右に伸ばす
    while (r < N) {
        if (x < sum + A[r]) break;
        sum += A[r];
        r++;
    }

    // 答えを加算
    ans += r - l;

    // 次から含まれなくなる要素を削る
    if (l < r) sum -= A[l];
    l++;
}

左端を進めるということは、一番左の要素を含めなくするということです。 ただし、限界まで$r$を伸ばしても$[l, r)$が空であるときにこれをすると不正なので、if (l < r)を入れています。

最後のステップです。 最初、$l \leq r$を仮定していましたが、$l$を右に進めるステップのせいで$r < l$になる可能性があります。 具体的には、$r$を伸ばした結果$[l, r)$が空($l = r$)であるとき、その次のステップで$r < l$になります。

これは都合が悪いため、最初に正規化を入れます。 忘れやすいので注意が必要です。

// クエリ入力
ll x; cin >> x;

int l = 0, r = 0;
ll sum = 0;

while (l < N) {
    // rの正規化
    if (r < l) r = l;

    // 右に伸ばす
    while (r < N) {
        if (x < sum + A[r]) break;
        sum += A[r];
        r++;
    }

    // 答えを加算
    ans += r - l;

    // 次から含まれなくなる要素を削る
    if (l < r) sum -= A[l];
    l++;
}

これで完成です。お疲れ様でした。

提出

例題2 : ABC38C - 単調増加

問題

長さ$N$の数列$a_1, a_2, \dots, a_N$が与えられる。 $a_l, a_{l+1}, \dots, a_r$が狭義単調増加となるような$(l, r)$の数を求めよ。

制約

• $1 \leq N \leq 10^5$
• $1 \leq a_i \leq 10^5$

こちらのほうが色々と条件がゆるいです。 まず、長さ1の列は狭義単調増加なので、空列について考えなくてよくなります。 さらに、「総和」のようなものがないので、左端を進める際に気にすることが無いです。 よって、次のような尺取りができます。

import std;

void main () {
    int N = readln.chomp.to!int;
    auto a = readln.split.to!(int[]);

    long ans = 0;
    int l = 0, r = 0;

    while (l < N) {
        // 空列はありえないので、なくても大丈夫
        if (r < l) r = l;

        while (r < N) {
            // l == rのときはとりあえず一つ右に進める
            if (l < r && a[r] <= a[r-1]) break;
            r++;
        }

        ans += r - l;

        // 左端を進める際にやることは無い
        l++;
    }

    writeln(ans);
}

提出

例題3 : ABC32C - 列

問題

長さ$N$の非負数列$S = (s_1, s_2, \dots, s_N)$と整数$K$が与えられる。次の条件を満たす空でない$S$の連続部分列の長さの最大値を求めよ。 条件を満たす連続部分列が存在しないときは$0$を出力せよ。

• 条件: 連続部分列の要素の総積が$K$以下

制約

• $1 \leq N \leq 10^5$
• $0 \leq K \leq 10^9$
• $0 \leq s_i \leq 10^9$

$S$に$0$が含まれているとき、$S$の総積は$0$になり、どんな$K$に対しても条件を満たします。 最初にそれを判定してしまいましょう。

$0$が含まれないとき、連続部分列が右に伸びるほど総積は増えるので、尺取りの条件を満たします。 空な区間/左側の処理どちらもありえるので、丁寧に処理しましょう。

import std;

 void main () {
     int N, K; readln.read(N, K);
     auto S = new int[](N);
     foreach (i; 0..N) S[i] = readln.chomp.to!int;

     solve(N, K, S);
 }

void solve (int N, int K, int[] S) {
    // 0を含むか？
    foreach (s; S) {
        if (s == 0) {
            writeln(N);
            return;
        }
    }

    // 右半開区間
    int ans = 0;
    long v = 1;
    int l = 0, r = 0;

    while (l < N) {
        // 区間がおかしい場合は空な区間で初期化
        if (r < l) r = l;

        // 可能な限り右を伸ばす
        while (r < N) {
            if (K < v * S[r]) break;
            v *= S[r];
            r++;
        }

        ans = max(ans, r - l);

        // 逆操作が必要ならして、左を一つ進める
        if (l < r) v /= S[l];
        l++;
    }

    writeln(ans);
}

void read (T...) (string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

提出

終わりに

右半開区間のありがたみを初めて感じたかもしれない… よくわからなくて苦手だったアルゴリズムだったけれど、意外と便利に感じました。 皆様もぜひどうぞ。