恒例の、対象読者さん紹介です。
- 尺取り法をよくバグらせてしまう方
- ログは定数！二分探索君！な方
目標
前世がヨクバリスですから、2 つです。
- 基本の実装が簡単にできます。
- 実装の本質部分を特定できていて、難しいものにもスムーズに応用ができます。
ただ、この記事ではあまり難しいお話はスキップです。具体的な応用については、他にたくさんの記事があります。ここでは、尺取り法のソウルを理解することに注力しましょう。
ご参考にどうぞです。
けんちょんさんです。
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
尺取り法とはなんですか？
ご存知の通り、数列に左手と右手で仕切りを 2 本入れて、どんどん右に動かしていくアルゴリズムです。
尺取り法の難しさは大きく分けて 2 つです。
- 左手、右手を動かしたときにどうなりますか？（クエリ処理パート）
- 左手、右手をどのように動かすと良いですか？（クエリに帰着するパート）
それでは、これらを順番にご説明して行きます。
尺取り法の難しいポイント 1.「左手、右手を動かしたときにどうなりますか？（クエリ処理パート）」
例です。
脳トレです。長さが $ N $ の数列 $A = \left ( A _ i \right ) _ { i = 0 } ^ { N - 1 } $ があります。せっかくですから、なにか書きましょうか。こちらです。
A = (20, 3, 5, 0, 7, 2)
- さて両手を広げてください。左手と右手で好きな範囲を抱えましょう。（私は $ (3, 5) $ です。）
- そこに含まれる数の総和を憶えてください。ここは頑張って計算です。（ $ 3 + 5 = 8 $ ですね。）
- はい、右手を一つ右に、今度は左手、次は右手、今度はまた右手です。（あわわ‥‥）
- さて、今の合計はいくつでしょうか？（ 答えは $ 5 + 0 + 7 + 2 $ で、$ 14 $ です！）
これを上手に実装するにはどうすればよいでしょう？ そうですね。変わった分だけを更新していけばよいです。
数学のお時間です。
数列 $A$ があって、次のようなクエリを処理したいです。
- 右手を右に
- 左手を右に
- さて、範囲の合計はいくつでしょうか？
これらのクエリに対応するために、必要な状態は 3 つです。
- 左手の位置 $ L $
- 右手の位置 $ R $
- 範囲の合計 $ X $
です。
ここで注意なのですが、範囲は左が閉、右が開で書いています。右手を動かすと $ A _ R $ が仲間に加わり、また左手を動かすと $ A _ L $ とお別れをすることになります。
すると、各クエリの処理は次のように書けます。
- 右手クエリ
- 合計に $ A _ R $ を足します。
- $ R $ をひとつ右に移動です。
- 左手クエリ
- 合計から $ A _ L $ を引きます。
- $ L $ をひとつ右に移動です。
- 合計クエリ
- 合計を知っていますか？ $ X $ が知っています。
これで、尺取り法のクエリパートはマスターです。さすがです。
尺取り法の難しいポイント 2.「左手、右手をどのように動かすと良いですか？（クエリに帰着するパート）」
いわゆる尺取り法と呼ばれるパターンは、次の 2 つのどちらかであることが多いです。
ここで大事な仮定なのですが、数列 $ A $ の要素はすべて $ 0 $ 以上です。
- 合計が $ K $ 以下であるような範囲の個数を求めましょう。
- 合計が $ K $ より大きいような範囲の個数を求めましょう。
var a = new int[]{20, 3, 5, 0, 7, 2};
int k = 8;
問題 1 の解き方です。
左端を全探索です。
- まずは、左手に意識を集中してください。まずは、$ 0 $ に左手を置きましょう。
- そして合計が $ K $ を超えないように気をつけながら、右手のポジショニングです。
- 右手が $ R $ まで進めたとしましょう。そうすると、はじめの $ R $ 個の区間はすべて条件を満たします。$ R $ ポイントを獲得です。
- 今です！ 左手を一つ進めましょう。
- そして、再び右手位置決めボーナスタイムです。新しい $ R $ に書き換えて、今度は左端が $ 1 $ ですから、 $ R - 1 $ ポイント獲得です。
- これを繰り返していくと良いです。
ところで、初めの右手ボーナスタイムで一つも進めなかったときにはどうでしょう。左手が右手を追い越してしまうことがありますね。悲しいです。本来はここで特殊な処理を入れるのが良いのですが‥‥いえ、そんなことは知りません。負の数を知っていますか？ 私は知っています。$ L = 1, R = 0, X = - A _ 0 $ です！（どーん）
はい、右手を好きなだけ動かして、左手を慎重にひとつだけ動かす。これぞ匠の技術です。ところでこれができるプログラミング言語の機能をご存知ですか？ そうです。for-loop です！
int n = a.Length, ans = 0;
for (int l = 0, r = 0, sum = 0; l < n; sum -= a[l++])
{
for (; r < n && sum + a[r] <= k; sum += a[r++]); // 右手さんの位置決めボーナスタイムです。
ans += r - l;
}
問題 2 の解き方です。
手の動きは完全に同じです。みなさんは賢いです。言葉は要りません。（はい！？）
変更点はここだけです。今度は外側をカウントです。$ K $ 以内に収まっていない区間は $ [ L, R + 1 [, \ [ L, R + 2 [, \dots, [ L, N [ $ ですから、ここで $ N - R $ ポイントを獲得です！
int n = a.Length, ans = 0;
for (int l = 0, r = 0, sum = 0; l < n; sum += a[l++])
{
for (; r < n && sum + a[r] <= k; sum += a[r++]); // 右手さんの位置決めボーナスタイムです。
ans += n - r; // 先程は r - l でした。
}
右手が最後まで到達してからは、$ 0 $ を足すだけの空回りですから、break をしてもよいです。もちろんしなくてもよいです。
これでクエリに帰着するパートも怖くありません。
今日からあなたは尺取り法マスターです！
数え上げではなく、最大最小ならばどのように書きますか？
鋭い皆さんならば分かってしまったかもしれませんが、問題 1 と問題 2 は合わせると全体ですから、片方が解けると、$ N ( N + 1 ) / 2 $ から引けば良いです。ご存知なのに黙っていてくださって、ありがとうございます。
では、こちらならばどうでしょう？
- 合計が $ K $ 以下であるような範囲の最大長さを求めましょう。
- 合計が $ K $ より大きいような範囲の最小長さを求めましょう。
この場合は、先程区間の長さを足していたところを、最大や最小にすると良いです。
- 問題 1
左手が $ L $ のときに、$ R $ までは伸ばして良いです。
int n = a.Length, ans = 0;
for (int l = 0, r = 0, sum = 0; l < n; sum -= a[l++])
{
for (; r < n && sum + a[r] <= k; sum += a[r++]);
ans = Math.Max(ans, r - l); // 変更点です。
}
- 問題 2
左手が $ L $ のときに、$ R $ よりも更に先まで伸ばせば OK ですから、$ R - L + 1 $ です。ここで注意なのですが、$ R = N $ のときにはこれ以上伸ばせませんから、break が必須です！
int n = a.Length, ans = 0;
for (int l = 0, r = 0, sum = 0; l < n; sum -= a[l++])
{
for (; r < n && sum + a[r] <= k; sum += a[r++]);
if (r == n) break; // 重要
ans = Math.Min(ans, r - l + 1); // 変更点です。
}
実装のバリエーションです。
尺取り法の共通部分です。こちらを書き換えていきましょう。
int n = a.Length;
for (int l = 0, r = 0, sum = 0; l < n; sum -= a[l++])
{
for (; r < n && sum + a[r] <= k; sum += a[r++]);
}
逆順です。
一身上の都合で逆順に計算したい方向けです。
この場合、問題 2 のパターンの長さが、$ N - R $ ではなく $ L - 0 $ です。
int n = a.Length;
for (int l = n, r = n, sum = 0; r > 0; sum -= a[--r])
{
for (; 0 < l && sum + a[l - 1] <= k; sum += a[--l]);
// ans += r - l; or ans += l;
}
r や sum を外に出して、インクリメントをブロックの中に入れます。
書き方が異なるだけで、まったく同じことです。こちらの方がわかりやすいという説もあります。さらに内側のループを while で書く方も多いです。
int n = a.Length, ans = 0;
int r = 0, sum = 0; // 追い出された方々です。
for (int l = 0; l < n; l++)
{
for (; r < n && sum + a[r] <= k; r++)
{
sum += a[r]; // 閉じ込められたインクリメントさんです。
}
sum += a[l]; // 閉じ込められたインクリメントさんです。
}
負数をご存じない方でも大丈夫です。
何らかの事情で $ L \leq R $ を破るわけに行かない場合は、仕方がありませんから、インクリメントで条件分岐です。
int n = a.Length;
for (int l = 0, r = 0, sum = 0; l < n;) // ここにあったインクリメントはブロックの中に行きました。
{
for (; r < n && sum + a[r] <= k; sum += a[r++]);
// ans += r - l など
if (l < r) sum -= a[l++]; // こちらです。
else { l++; r++; } // そしてこちらが、負の数回避です。
}
C++ のカンマ演算子、条件演算子でも良いです。（for さんが定員オーバーで悲鳴を上げています。）
int n = a.size();
for (int l = 0, r = 0, sum = 0; l < n; l < r ? sum -= a[l++] : (l++, r++)) {
for (; r < n && sum + a[r] <= k; sum += a[r++]);
}
さらなるパターン
けんちょんさんの記事をご覧いただけると良いです。（手抜き）👉 1-1. しゃくとり法が使える場面
こちらの記事でも言及されているとおり、「和が $ K $ 以下である」以外の条件でも使えます。
尺取り法が使えるために大切なことは、
- 左手を固定したときに、ちょうど境目になるような右手の位置が決まります。
- 左手をひとつ進めたときに、右手が戻ることがありません。
の 2 点です。
最後に、ただの尺取り法では難しいパターンのご紹介です。
また、状態がうまく管理できるかどうかというのも重要です。今回は総和でしたが、たとえば Max ならばいかがでしょう。GCD なら？ bitwise or なら？ 難しいです。
これらには、引き算のようなものがありませんから、$ A _ L $ とお別れができません。メンヘラですね。これらのような Aggregation 系の設定は、尺取り法をさらに発展させた、手を三本使用した火星人以外お断り天才アルゴリズムで統一的に対応することが出来るのですが、こちらは次回以後のお楽しみです。（なお、Max は重複度付き集合を管理することで普通の尺取り法で頑張ることもできます。）
ごあいさつ
こんな、シーケンシャルアルゴリズムなのに図の一つもない記事を最後までお読み頂き、ありがとうございます。この涙は尺取り法の実装で嵌ったあの日の涙です。