コンテンツにスキップ

スライド最小値

タグ「スライド最小値」の記事 2 件

スライド最小値のリンク集

スライド最小値について、参考になる記事や資料をまとめました。

スライド最小値は、数列の上で長さ KK の窓を 1 つずつ右にずらしながら、各窓の最小値を求める手法です。deque(両端キュー)に添字を入れ、対応する値が単調増加になるように保ちます。新しい要素を入れる前に、末尾からその値以上の要素を捨て、窓から外れた添字は先頭から捨てます。すると deque の先頭が窓の最小値になります。各要素は 1 回入って高々 1 回出るだけなので、全体で O(N)O(N) です。窓の左端と右端がどちらも単調に動くなら、窓の幅が変わっても使えます。最大値のときは不等号を逆にします。

deque には値ではなく添字を入れると、先頭が窓から外れたかどうかを添字で判定できます。値だけを入れる実装もありますが、そのときは末尾から捨てるのを「より大きい」値に限り、同じ値を残す必要があります。また、窓の端が戻る(単調に動かない)区間最小値ならセグメント木やスパーステーブル、最小値以外の演算を窓の上でまとめたいなら、下で紹介する SWAG を使います。

  • スライド最大(最小)値・ヒストグラム内最大長方形問題を俯瞰する(kuuso1、Qiita)
    • 数値を戦闘力、窓に入ることを入学、出ることを卒業にたとえ、「番長の順番待ち」が deque で表せることを図で説明しています。添字を deque に入れる Python の実装があります。後半では、卒業のない場合としてスタックを使うヒストグラム内最大長方形問題を扱っています。
    • コードは最大値版だけです。
  • スライド最小値、SWAG(いかたこのたこつぼ)
    • 区間の値を求める手法(累積和、セグメント木、スパーステーブル、Mo’s Algorithm など)を表で比べたうえで、スライド最小値の deque の変化を具体例の表で追っています。後半は下の SWAG の説明で、Python の実装があります。例題は載っていません。

尺取り法・スライディングウィンドウとの関係

Section titled “尺取り法・スライディングウィンドウとの関係”
  • しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
    • しゃくとり法の解説記事です。「3-3. スライド最小値や Convex Hull Trick」の節で、区間の両端が単調に動くなら最小値を取る添字も単調に動くので、しゃくとり法のように処理できると説明しています。(値, 時刻) の組を deque に入れる C++ の SlideMin 構造体があります。
  • Sliding Window(USACO Guide、英語)
    • 前半は固定長の窓と、尺取り法による可変長の窓を sorted set で扱います。後半の「Sliding Window Maximum in O(N)O(N)」で、単調な deque(添字を持つ版と値を持つ版)と 2 つのスタックによるキューを説明しています。C++・Java・Python のコードと、問題の一覧があります。
    • 説明とコードは最大値版です。

スライド最小値は min や max にしか使えませんが、キューを 2 つのスタックで表し、それぞれのスタックで累積の値を持つと、結合法則を満たす任意の演算で「末尾に追加」「先頭を削除」「全体の値を求める」がならし O(1)O(1) でできます。これを SWAG と呼びます。

  • Foldable-Queue(SWAG) およびそのDeque版について(Shirotsume、Qiita)
    • 2 つのスタックでキューを作る方法、累積の値を持つスタック、それらを組み合わせた SWAG を順に説明しています。両端から出し入れできる Deque 版も扱っています。Python の実装があります。
  • Sliding Window Aggregation(data-structures、Scrapbox)
    • 操作と計算量、仕組みを短くまとめたページです。min については deque を使う別の方法(スライド最小値)があることにも触れています。参考文献と問題の一覧があります。

スライド最小値や SWAG を扱う講座はまだありません。窓の幅が固定でない区間最小値を求めたいときは、スパーステーブルの講座が参考になります。前計算 O(Nlog⁡N)O(N \log N) で、任意の区間の最小値に O(1)O(1) で答える方法です。

  • collections.deque(Python 公式ドキュメント)
    • deque は両端での追加と削除(append、appendleft、pop、popleft)がおよそ O(1)O(1) でできます。リストの pop(0) は O(n)O(n) なので、先頭から捨てる処理にはこちらを使います。添字によるアクセスは、両端なら O(1)O(1) ですが、中央付近では O(n)O(n) です。「deque のレシピ」の節には、窓の和を差分で更新する移動平均の例があります。
  • スライド最小値(Slide-Min)(Luzhiled’s memo)
    • C++ の実装で、slide_min(v, k) が長さ kk の各窓の最小値を返します。DP の高速化に使う例題の検証コードつきです。
  • Double-ended queue(英語版 Wikipedia)
    • 「Monotonic queue」の節で、単調な deque によるスライド最大値の O(n)O(n) の求め方を C++ のコードつきで説明し、DP の高速化や最小値つきのキュー(min-queue)にも触れています。スライド最小値だけの記事はなく、日本語版の「両端キュー」にはこの話はありません。
    • 最初のコード例は、引数の型が std::vector<int> &seq[] となっていて、そのままではコンパイルできません。
  • Minimum stack / Minimum queue(cp-algorithms)
    • 最小値つきのスタックとキューの作り方を説明しています。キューは、値だけを持つ deque、(値, 添字) を持つ deque、2 つのスタックの 3 通りです。最後に、固定長の窓の最小値がこれらで O(n)O(n) で求まることを示しています。C++ のコード断片で、値は int です。
  • Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
    • 8 章「Amortized analysis」の 8.3 節「Sliding window minimum」で、8.2 節の「最も近い小さい要素」をスタックで求める方法と同じ考え方として、キューの変化を図で説明しています。コードはありません。
  • yukicoder contest 517 D - Streaming Schedule
    • 「休む日」についての DP の遷移を累積和で変形し、長さ C−1C - 1 の窓の最大値を deque によるスライド最大値で求めています。deque に添字ではなく値を入れる実装です。

yukicoder contest 517 D - Streaming Schedule

NN 日間、毎日「配信する」か「休む」かを選びます。ii 日目に配信するとファンが AiA_i 人増え、休むと何も起きません(1≤Ai≤1091 \le A_i \le 10^9)。

ただし、BB 日以上続けて休むことはできず、CC 日以上続けて配信することもできません(2≤B,C≤N+12 \le B, C \le N + 1)。増えるファンの人数の最大値を求めてください(N≤3×105N \le 3 \times 10^5)。

配信が続く区間を「配信区間」と呼びます。配信区間の長さは C−1C - 1 以下、休みが続く区間の長さは B−1B - 1 以下でなければなりません。

3 日以上続く休みは考えなくてよい

Section titled “3 日以上続く休みは考えなくてよい”

Ai≥1A_i \ge 1 なので、配信する日は多いほうが得です。3 日以上続く休みがあれば、その真ん中の 1 日を配信に変えられます。この日の両隣は休みのままなので、長さ 1 の配信区間ができるだけです。C≥2C \ge 2 なので長さ 1 の配信区間は必ず許され、休みの区間も短くなるだけなので、条件は崩れません。しかもファンは増えます。

したがって、最適解では休みは 2 日までしか続きません。B=2B = 2 なら連続休みは 1 日まで、B≥3B \ge 3 なら 2 日まで許されます。以下では、B≥3B \ge 3 のときは連続休みの長さに上限を設けずに計算します。上限を超える休み方は、真ん中を配信に変えたものより必ず悪いので、最大値は変わりません。

resti\mathrm{rest}_i を「ii 日目に休むときの、ii 日目までのファンの増加数の最大値」とします。ii 日目に休む直前の状況で場合分けします。

  • 前日も休み:resti−1\mathrm{rest}_{i-1}。B≥3B \ge 3 のときだけ選べます。
  • 前日まで配信区間:配信区間が jj 日目から i−1i - 1 日目までなら、j−1j - 1 日目は休みです。値は restj−1+(Aj+⋯+Ai−1)\mathrm{rest}_{j-1} + (A_j + \dots + A_{i-1}) で、配信区間の長さの制約から i−(C−1)≤j≤i−1i - (C - 1) \le j \le i - 1 です。
  • ii 日目が 1 日目:何もしていないので 00 です。

1 日目より前の日を「0 日目に休んだ」とみなして rest0=0\mathrm{rest}_0 = 0 とおくと、配信区間が 1 日目から始まる場合も 2 つ目の式で扱えます。ただし、1 日目に休むときに「前日も休み」の場合として扱うと、B=2B = 2 では選べなくなってしまいます。そこで 1 日目に休む場合は、BB によらず 00 とします(下の補足も参照)。

最終日に休む場合の答えは restN\mathrm{rest}_N、最終日まで配信する場合の答えは jj 日目から NN 日目までの配信区間を使った同じ式で求まります。

累積和 Si=A1+⋯+AiS_i = A_1 + \dots + A_i を使うと、2 つ目の式は

restj−1+Si−1−Sj−1=(restj−1−Sj−1)+Si−1\mathrm{rest}_{j-1} + S_{i-1} - S_{j-1} = (\mathrm{rest}_{j-1} - S_{j-1}) + S_{i-1}

と書けます。ii が 1 増えると、jj の範囲は 1 つずつ右にずれます。したがって、長さ C−1C - 1 の窓の中での restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} の最大値が分かればよく、これは deque を使ったスライド最大値で求まります。

計算量は O(N)O(N) です。

最初は 1 日目に休む場合も「前日も休み」として扱っていて、WA になりました。たとえば N=2,B=2,C=2,A=(8,9)N = 2, B = 2, C = 2, A = (8, 9) では、1 日目に休んで 2 日目に配信する 99 が正解です。しかし、1 日目の休みを「0 日目からの連続休み」とみなすと、B=2B = 2 で禁止されて 88 になってしまいます。0 日目は実際には休みではないので、1 日目だけは BB によらず休めるようにする必要があります。

Python
from collections import deque
N, B, C = map(int, input().split())
A = list(map(int, input().split()))
t = 0
k = 0
d = deque()
e = deque()
for i, a in enumerate(A):
if d:
u = e[0] + k
else:
u = -(10**18)
if B > 2 or i == 0:
u = max(u, t)
d.append(t - k)
e.append(t - k)
while len(e) >= 2 and e[-2] < e[-1]:
x = e.pop()
e.pop()
e.append(x)
k += a
while len(d) >= C:
x = d.popleft()
if len(e) > 0 and e[0] == x:
e.popleft()
t = u
print(max(t, max(d) + k))

変数の意味は次のとおりです。

  • t:前日に休んだときの最大値(resti−1\mathrm{rest}_{i-1})
  • k:前日までの累積和(Si−1S_{i-1})
  • u:その日に休んだときの最大値(resti\mathrm{rest}_i)
  • d:配信区間の始まりの候補 jj について、restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} を並べた窓。最大 C−1C - 1 個を持ちます。
  • e:d のうち、後ろにより大きい値がないものだけを残した deque。先頭が窓の中の最大値です。

d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 xx が e から消えているなら、xx より後に xx より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は xx より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。