スライド最小値のリンク集
スライド最小値について、参考になる記事や資料をまとめました。
スライド最小値は、数列の上で長さ の窓を 1 つずつ右にずらしながら、各窓の最小値を求める手法です。deque(両端キュー)に添字を入れ、対応する値が単調増加になるように保ちます。新しい要素を入れる前に、末尾からその値以上の要素を捨て、窓から外れた添字は先頭から捨てます。すると deque の先頭が窓の最小値になります。各要素は 1 回入って高々 1 回出るだけなので、全体で です。窓の左端と右端がどちらも単調に動くなら、窓の幅が変わっても使えます。最大値のときは不等号を逆にします。
deque には値ではなく添字を入れると、先頭が窓から外れたかどうかを添字で判定できます。値だけを入れる実装もありますが、そのときは末尾から捨てるのを「より大きい」値に限り、同じ値を残す必要があります。また、窓の端が戻る(単調に動かない)区間最小値ならセグメント木やスパーステーブル、最小値以外の演算を窓の上でまとめたいなら、下で紹介する SWAG を使います。
まず読むもの
Section titled “まず読むもの”- スライド最大(最小)値・ヒストグラム内最大長方形問題を俯瞰する(kuuso1、Qiita)
- 数値を戦闘力、窓に入ることを入学、出ることを卒業にたとえ、「番長の順番待ち」が deque で表せることを図で説明しています。添字を deque に入れる Python の実装があります。後半では、卒業のない場合としてスタックを使うヒストグラム内最大長方形問題を扱っています。
- コードは最大値版だけです。
- スライド最小値、SWAG(いかたこのたこつぼ)
- 区間の値を求める手法(累積和、セグメント木、スパーステーブル、Mo’s Algorithm など)を表で比べたうえで、スライド最小値の deque の変化を具体例の表で追っています。後半は下の SWAG の説明で、Python の実装があります。例題は載っていません。
尺取り法・スライディングウィンドウとの関係
Section titled “尺取り法・スライディングウィンドウとの関係”- しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
- しゃくとり法の解説記事です。「3-3. スライド最小値や Convex Hull Trick」の節で、区間の両端が単調に動くなら最小値を取る添字も単調に動くので、しゃくとり法のように処理できると説明しています。(値, 時刻) の組を deque に入れる C++ の
SlideMin構造体があります。
- しゃくとり法の解説記事です。「3-3. スライド最小値や Convex Hull Trick」の節で、区間の両端が単調に動くなら最小値を取る添字も単調に動くので、しゃくとり法のように処理できると説明しています。(値, 時刻) の組を deque に入れる C++ の
- Sliding Window(USACO Guide、英語)
- 前半は固定長の窓と、尺取り法による可変長の窓を sorted set で扱います。後半の「Sliding Window Maximum in 」で、単調な deque(添字を持つ版と値を持つ版)と 2 つのスタックによるキューを説明しています。C++・Java・Python のコードと、問題の一覧があります。
- 説明とコードは最大値版です。
SWAG(Sliding Window Aggregation)
Section titled “SWAG(Sliding Window Aggregation)”スライド最小値は min や max にしか使えませんが、キューを 2 つのスタックで表し、それぞれのスタックで累積の値を持つと、結合法則を満たす任意の演算で「末尾に追加」「先頭を削除」「全体の値を求める」がならし でできます。これを SWAG と呼びます。
- Foldable-Queue(SWAG) およびそのDeque版について(Shirotsume、Qiita)
- 2 つのスタックでキューを作る方法、累積の値を持つスタック、それらを組み合わせた SWAG を順に説明しています。両端から出し入れできる Deque 版も扱っています。Python の実装があります。
- Sliding Window Aggregation(data-structures、Scrapbox)
- 操作と計算量、仕組みを短くまとめたページです。min については deque を使う別の方法(スライド最小値)があることにも触れています。参考文献と問題の一覧があります。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”スライド最小値や SWAG を扱う講座はまだありません。窓の幅が固定でない区間最小値を求めたいときは、スパーステーブルの講座が参考になります。前計算 で、任意の区間の最小値に で答える方法です。
Python
Section titled “Python”- collections.deque(Python 公式ドキュメント)
dequeは両端での追加と削除(append、appendleft、pop、popleft)がおよそ でできます。リストのpop(0)は なので、先頭から捨てる処理にはこちらを使います。添字によるアクセスは、両端なら ですが、中央付近では です。「deque のレシピ」の節には、窓の和を差分で更新する移動平均の例があります。
- スライド最小値(Slide-Min)(Luzhiled’s memo)
- C++ の実装で、
slide_min(v, k)が長さ の各窓の最小値を返します。DP の高速化に使う例題の検証コードつきです。
- C++ の実装で、
百科事典・英語の資料
Section titled “百科事典・英語の資料”- Double-ended queue(英語版 Wikipedia)
- 「Monotonic queue」の節で、単調な deque によるスライド最大値の の求め方を C++ のコードつきで説明し、DP の高速化や最小値つきのキュー(min-queue)にも触れています。スライド最小値だけの記事はなく、日本語版の「両端キュー」にはこの話はありません。
- 最初のコード例は、引数の型が
std::vector<int> &seq[]となっていて、そのままではコンパイルできません。
- Minimum stack / Minimum queue(cp-algorithms)
- 最小値つきのスタックとキューの作り方を説明しています。キューは、値だけを持つ deque、(値, 添字) を持つ deque、2 つのスタックの 3 通りです。最後に、固定長の窓の最小値がこれらで で求まることを示しています。C++ のコード断片で、値は
intです。
- 最小値つきのスタックとキューの作り方を説明しています。キューは、値だけを持つ deque、(値, 添字) を持つ deque、2 つのスタックの 3 通りです。最後に、固定長の窓の最小値がこれらで で求まることを示しています。C++ のコード断片で、値は
- Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
- 8 章「Amortized analysis」の 8.3 節「Sliding window minimum」で、8.2 節の「最も近い小さい要素」をスタックで求める方法と同じ考え方として、キューの変化を図で説明しています。コードはありません。
- CSES - Sliding Window Minimum:長さ の各窓の最小値を求めます。 で入力は式で生成され、最小値の XOR を出力します。
- Library Checker - Queue Operate All Composite:キューに入っている一次関数すべての合成を求めます。SWAG の verify 用です。
- AtCoder Weekday Contest 0045 Beta E - 区間の評価値:長さ の窓の総和と最小値を、窓をずらしながら求めます。
- ABC352 D - Permutation Subsequence:逆順列の長さ の窓で、最大値と最小値の差の最小値を求めます(公式解説)。
- ABC228 F - Stamp Game:2 次元の窓の最大値を、行ごと・列ごとのスライド最大値で求めます(公式解説)。
- ABC146 F - Sugoroku:ゴールから逆向きに、各マスからの最短手数を幅 の窓の最小値で求められます。
- 競プロ典型 90 問 037 - Don’t Leave the Spice(★5):ナップサック DP の遷移が区間の最大値なので、スライド最大値で にできます。
- CODE FESTIVAL 2016 Tournament Round 3(Parallel)A - ストラックアウト:直前に当てたパネルから 以内という遷移の DP を、スライド最大値で高速化します。
- ABC269 G - Reversible Cards 2:個数制限つきナップサックの DP です。公式解説の本筋は別の方法ですが、スライド最小値や SWAG を使う別解にも触れています(公式解説)。
- AGC038 B - Sorting a Segment:長さ の各窓の最小値・最大値を使って、隣り合う操作の結果が同じになるかを判定します(公式解説)。
このブログの記事
Section titled “このブログの記事”- yukicoder contest 517 D - Streaming Schedule
- 「休む日」についての DP の遷移を累積和で変形し、長さ の窓の最大値を deque によるスライド最大値で求めています。deque に添字ではなく値を入れる実装です。