尺取り法・sliding windowで連続区間を走査する

概要

尺取り法・sliding window

連続区間の左端を一つ進めたとき、必要な右端も前へ進むだけなら、毎回最初から探し直す必要はない。二つの端点と区間内の情報を保ち、全体を一走査で調べるのが尺取り法である。二列の圧縮された区間を同じ位置で照合する走査も、この単元で扱う。

考え方

縮めても合法なら、最大の右端を追う

配列を0始まりの A0,…,AN−1A_0,\ldots,A_{N-1} とし、窓を半開区間 [L,R)[L,R) で表す。入っているのは AL,…,AR−1A_L,\ldots,A_{R-1} で、RR は次に追加する位置、L=RL=R は空窓である。

正数列 A=(2,1,3,2)A=(2,1,3,2) で、和が4以下の最長区間を探そう。最初は L=R=0L=R=0、和0である。2と1を加えると [0,2)[0,2)、和3になるが、次の3を加えると6なので止める。その後は左の要素を除き、再び右へ広げる。

左端 LL左の要素を除いた直後の窓と和拡張後の最大窓と和止まる理由
0空、0[0,2)[0,2)、3次の3を加えると6
1[1,2)[1,2)、1[1,3)[1,3)、4次の2を加えると6
2[2,3)[2,3)、3[2,3)[2,3)、3次の2を加えると5
3空、0[3,4)[3,4)、2配列の末尾

各左端の長さ R−LR-L の最大値は2となる。正数の和なので、右へ広げると和は増え、縮めると減る。一つ追加して上限を超えたら、その先まで広げても合法には戻らない。

一般にも、合法な区間のどの部分区間も合法なら、この手順で各左端の最大右端を求められる。前の最大窓から左端を一つ除いた窓も合法なので、次の最大右端は前の右端より左には来ない。この不変条件が、右端を戻さずによい理由である。

実装では、R<NR<N かつ ARA_R を追加しても合法な間だけ、集計値へ追加して RR を進める。窓を評価した後、非空なら ALA_L を削除して LL を進める。一要素も追加できなければ R=LR=L の空窓のままなので、存在しない ALA_L を削除しない。L,RL,R をともに次の位置へ進め、集計値は空の状態に保つ。例えば上限4で要素が7なら、この処理が必要になる。非空区間を求める問題では、空窓を長さ0の解として採用するか、解なしとして扱うかも区別する。

広げても合法なら、最小の右端を追う

同じ正数列で、今度は「和が4以上になる最短区間」を探す。これは広げるほど条件を満たしやすいので、初めて和が4以上になったところで止める。

  • L=0L=0 では、和は2、3、6と増える。最小右端は R=3R=3、窓は [0,3)[0,3) である。
  • 左の2を除くと [1,3)[1,3) の和は4なので、L=1L=1 でも R=3R=3 のままでよい。
  • 左の1を除くと和3になる。次の2を追加して、L=2L=2 の最小窓は [2,4)[2,4)、和5となる。
  • 左の3を除くと和2で、もう追加できない。L=3L=3 では条件を満たす右端がない。

各左端で条件を満たした窓の長さを比較すると、最短長は2である。最大右端を探す場合と違い、窓が不成立の間に広げ、成立したら止める。末尾まで広げても不成立なら、その窓は答えに使わない。

手順は空窓と空の集計値から始め、各左端で条件成立まで追加し、成立した窓を評価してから左の要素を除く。空窓も条件を満たす設定では、長さ0を答えとして許すかを先に決める。空窓からは要素を削除せず、次の左端と同じ位置へ右端も合わせる。

一般に、合法な区間を含む大きな区間も合法なら、最小右端は後退しない。前の最小右端より手前で切った区間はすべて不成立だった。その左端を除いて縮めても、成立することはない。もし縮めた区間が合法なら、それを含む元の区間も合法になってしまうからである。左端の削除後も成立していればその右端が最小で、崩れた場合だけ拡張を再開すればよい。末尾まで不成立なら、以後の左端でも成立しない。

ABC260 Eの「すべての組の少なくとも一端を含む」はこの型である。各組の被覆回数と、被覆済みの組数を保ち、全組を覆うまで広げる。ABC258 Eの「重量が閾値以上になる」も最小右端の型である。円環では列を二周分並べ、大きな閾値は完全周回分と余りへ分けて、残りの端点移動を線形に抑える。余り0なら追加区間は空で、窓から要素を削除する必要もない。

ABC250 Fも、凸多角形の切片面積が目標以上になる最初の右端を追う。ただし求めるのは最短長ではなく目標との面積差なので、目標を跨ぐ前後の候補を比較する。各問題の解説では、その問題が半開区間か両端を含む区間かも確認しよう。

負数を含む和では境界が一つにならない

和の上限4に対して A=(3,3,−3)A=(3,3,-3) を考える。左端0からの和は3、6、3であり、合法・不合法・合法と変わる。上限を超えた時点で打ち切ると、長さ3の合法区間を見逃す。左端を除いても負数なら和が増えるため、縮小で合法性を保つ議論も使えない。

負数を含む配列がすべて尺取りに不向きなのではなく、今回追いたい条件が、区間の伸縮に対してどちら向きに保存されるかを証明する必要がある。条件名が「区間和」だからという理由だけで、同じ手順を転用しない。

RLEは、二列の値の組が一定な区間をマージする

連長圧縮(RLE)は、同じ値が連続する部分を「値と長さ」の組で持つ表現である。一つの連続部分をrunと呼ぶ。ABC294 Eでは、二列を展開せず、同じ位置の値が等しい長さを数えたい。

例えば一列目が (1,3),(2,2)(1,3),(2,2)、二列目が (1,1),(2,4)(1,1),(2,4) なら、最初の1位置は値の組が (1,1)(1,1)、次の2位置は (1,2)(1,2)、最後の2位置は (2,2)(2,2) である。等しい位置は合計3個となる。変化が起きるのは、どちらかのrunが終わる位置だけである。

両列の未処理部分が同じ位置から始まるようにし、現在runの残長を p,qp,q とする。min⁡(p,q)\min(p,q) だけ処理し、値が等しければその長さを答えへ加える。両残長から処理長を引き、0になった側だけ次のrunへ進む。同時に0なら両方を進める。

これは、二列のrun境界をマージして「値の組が一定な区間」へ分割する操作である。合法窓の最大・最小右端を探す処理とは目的が異なるが、各ポインタを戻さず、少なくとも片方を前へ進めることで全体の費用を抑える点が共通している。

成立条件と計算量

長さ NN の一列を走査すると、両端はそれぞれ高々 NN 回進む。追加・削除・条件確認・窓の評価が一回 TT で行えるなら時間は O(NT)O(NT)、和のように T=O(1)T=O(1) なら O(N)O(N) である。二周配列でも端点移動は O(N)O(N)。ただし各更新で集合やFenwick Treeを使うなら、その費用を掛ける。ABC260 Eのように一座標の追加で複数の組を更新する場合は、一更新を定数時間とせず、全座標に属する組の出現数を合計して評価する。

RLEのrun数をそれぞれ N1,N2N_1,N_2 とすると、各回で少なくとも一runが終わるため時間は O(N1+N2)O(N_1+N_2)。展開後の長さには比例しない。入力を保存する空間は一列なら O(N)O(N)、RLEなら O(N1+N2)O(N_1+N_2) で、和や現在runの残長だけなら走査用の追加空間は O(1)O(1)。頻度表などを使うときはその領域も加える。

二つの端点を使うという形よりも、保持する集計値、合法性が保存される向き、右端が後退しない証明を先に確認する。単調探索で各左端の境界を個別に二分探索する代わりに、隣の左端の探索結果を再利用できるか、という視点も持っておこう。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。窓の条件とpointerが戻らない理由を定め、全体の走査回数を数える。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-two-pointers-window

習得する技能

  • 一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

窓の不変条件と左右端の単調性を使い、各要素を高々定数回だけ処理して連続区間を列挙する。

このUnitでは扱わないもの

  • 値域上の真偽境界を探す二分探索・パラメトリックサーチ。

根拠