尺取り法のリンク集
尺取り法(しゃくとり法)について、参考になる記事や資料をまとめました。
尺取り法は、数列の区間 の左端と右端をどちらも右にだけ動かしながら、条件を満たす区間を調べる手法です。「区間が条件を満たすなら、それに含まれる区間も満たす」(または「それを含む区間も満たす」)という単調性があると、左端 ごとの右端の境目が について単調になります。そのため、右端を伸ばせるだけ伸ばし、次に左端を 1 つ縮める、を繰り返すと、全体で 回の操作で済みます。条件を満たす区間の最大長・最小長・個数を求めるときによく使われます。
区間の和で判定するときは、値が非負(正)であることが単調性の前提です。負の値があると使えないので、累積和と二分探索やデータ構造を組み合わせる方法を考えます。また、ソートした配列の両端から 2 本のポインタを寄せていく方法も、two pointers と呼ばれます。
まず読むもの
Section titled “まず読むもの”- しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
- 尺取り法が使える場面を「条件を満たす区間の最小長・最大長・個数」の 3 つに整理し、AOJ DSL_3_C を例に、素朴な の方法から「右端の境目が左端について広義単調増加」という観察を経て にするまでを、図と C++ のコードで説明しています。使える条件、二分探索との類似、スライド最小値や Convex Hull Trick との関係まで扱い、最後に AtCoder などの問題例が並んでいます。
- 細かい誤記がいくつかあります。たとえば最後の問題「L番目のK番目の数」の出典が、冒頭では JOI 2017 予選 E、本文では予選 F となっています(AtCoder 上では JOI 2018 予選 F)。また、ABC098 D の問題概要は「正の整数列」とありますが、実際は も含みます。
- 競プロ典型 90 問 034 の解説(E869120、画像)
- 値の種類が 以下の最長の区間を求める問題を例に、左端 ごとの右端の限界 を表にし、 という単調性から操作が合計 回で済むことを 1 枚で説明しています。C++ の解答コードと、類題の一覧もあります。
- しゃくとり法のDequeを使ったバグりにくい実装(keroru、Qiita)
- 添字を動かす代わりに、右端の要素を deque に入れ、条件を満たさない間は先頭から取り出す実装を、ABC032 C を例に Python で説明しています。deque の中身の推移をデバッグ出力で見せ、一般形のテンプレートも載せています。単調性の説明はないので、上の記事とあわせて読んでください。
- 尺取り法の実装で嵌ったあの日の涙を数え切れないあなたにお送りする、尺取り法実装の † ソウル † です。(ngtkana、Qiita)
- 尺取り法の難しさを「左右の端を動かしたときの状態の更新」と「どう動かすか」に分けて、和が 以下・ より大きい区間の数え上げ、最大長・最小長などを C# で書き分けています。要素が 以上であることを「大事な仮定」として明示しています。図はありません。
- コードにそのままでは誤答になる誤りがあります。和が 以下の区間を数えるコードで、左端を進めるときに
sum += a[l++]となっている箇所(正しくは-=)、最小長のコードでansを で初期化したままMath.Minを取っている箇所などです。
関連するリンク集
Section titled “関連するリンク集”- 二分探索のリンク集:左端ごとの右端の境目は、累積和の上の二分探索でも求められます。尺取り法より が付きますが、考えやすいこともあります。
- 累積和・いもす法のリンク集:区間の和の判定や、区間内の特定の要素の個数を で求めるのに使います。
- スライド最小値のリンク集:両端が単調に動く区間の最小値・最大値を deque で求める手法で、尺取り法と組み合わせてよく使われます。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”尺取り法を扱う講座はまだありません。競技プログラミング基本用語集の 6.2「区間」(半開区間の表記)、6.3「部分列,部分配列(連続部分列)」、6.6「単調性」の節で、関連する用語を確認できます。
日本語版・英語版の Wikipedia には、尺取り法(two pointers)の記事はありません。
- Two Pointers(USACO Guide)
- 両端から寄せる型(ソートした配列で和が になる 2 要素を探す CSES Sum of Two Values)と、同じ向きに動かす型(Codeforces 279B Books)を、表やアニメーションで説明しています。C++・Java・Python のコードと、12 問の問題一覧があります。
- 末尾の小テストは、two pointers を「2 つの添字の組を探す手法」とする選択肢だけを正解にしていて、本文の同じ向きに動かす型と噛み合いません。
- Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
- 8 章「Amortized analysis」の 8.1 節「Two pointers method」で、正の整数の列で和がちょうど の区間を探す問題と、2SUM(和が になる 2 要素)を図で説明しています。コードはありません。8.3 節はスライド最小値です。
- Two Pointers Method(Codeforces EDU)
- ITMO Academy の講座の 1 レッスンです。中身を見るには Codeforces へのログインが必要です。
左端を 1 つ進めるたびに右端を伸ばせるだけ伸ばす、という基本の形の問題です。
- AOJ DSL_3_A - The Smallest Window I:正の整数の列で、和が 以上の最短の区間の長さを求めます。
- AOJ DSL_3_B - The Smallest Window II: から までをすべて含む最短の区間の長さを求めます。
- AOJ DSL_3_C - The Number of Windows:和が 以下の区間の個数を、クエリごとに求めます。drken の記事の例題です。
- ABC130 D - Enough Array:正の整数の列で、和が 以上の区間の個数を数えます。公式解説は尺取り法と二分探索の両方を挙げ、尺取り法をすすめています(公式解説)。
- ABC038 C - 単調増加:狭義単調増加になっている区間の個数を数えます(公式解説)。
- ARC022 B - 細長いお菓子:同じ値を 2 つ含まない最長の区間を求めます(公式解説)。
- CSES - Playlist:上の ARC022 B と同じ形で、値が まであります。
- CSES - Subarray Sums I:正の整数の列で、和がちょうど の区間の個数を数えます。
- ABC032 C - 列:積が 以下の最長の区間を求めます。 を含むときに注意が必要です。公式解説の本筋は別の方法で、尺取り法は別解として図つきで説明されています(公式解説)。
- ABC229 D - Longest X:
.を 個までXに変えたときの、Xの最長の連続を求めます。公式解説に尺取り法そのものの説明と擬似コードがあります(公式解説)。 - 競プロ典型 90 問 034 - There are few types of elements(★4):値の種類が 以下の最長の区間を求めます(解説は上の「まず読むもの」)。
- ABC098 D - Xor Sum 2:区間の xor と和が等しい区間の個数を数えます。各ビットが区間内で高々 1 回しか立たない、と言い換えると尺取り法が使えます(公式解説)。
- ABC381 D - 1122 Substring:各値がちょうど 2 回ずつ隣り合って並ぶ最長の区間を求めます。偶数番目と奇数番目から始まるものに分け、2 項ずつ伸ばします(公式解説)。
ソートした配列の上で 2 本のポインタを動かす形の問題です。
- CSES - Sum of Two Values:和が になる 2 要素を探します。ソートして両端から寄せます。
- ABC326 C - Peak:数直線上の点に長さ の区間を置いて、含まれる点の最大数を求めます。公式解説は尺取り法と二分探索の両方を挙げています(公式解説)。
- ABC353 C - Sigma Problem:ソートしたあと、和が 以上になる組の個数を 2 本のポインタで数えます(公式解説)。
- ABC366 E - Manhattan Multifocal Ellipse:公式解説が「尺取り法の練習問題」としている、少し難しい問題です(公式解説)。
このブログの記事
Section titled “このブログの記事”- ABC481 E - Most Brilliant Starry Sky
- 星を偏角の順に並べ、偏角に を足した写しを後ろにつなげた列の上で、偏角の幅が 未満の区間を尺取り法で求めています。円環の上の尺取り法の例です。