単調進行による償却解析

概要

一回の操作に長いwhileループがあっても、各反復で一つの要素が次の段階へ進み、元の段階へ戻らないなら、全操作を通じた反復数を抑えられる。まず各反復を追加された要素へ対応させ、次に一反復あたりの費用を数える。

考え方

queueからheapへ、一度だけ移す

ABC217 E「Sorting Queries」では、列の末尾への追加、先頭の出力・削除、列全体の昇順ソートを行う。毎回全体をソートすると、同じ要素を繰り返し処理してしまう。必要なのは先頭の値なので、最後のソートまでにあった部分を最小値を取り出すheap、その後に追加した部分を到着順のqueueで持つ。

常に「heap内の要素を昇順に並べた列、その後ろにqueueの列を連結したもの」が現在の列になるよう保つ。追加はqueueの末尾へ入れる。ソートはqueueが空になるまで先頭をheapへ移す。出力・削除はheapが非空ならその最小値、空ならqueueの先頭を取り出す。これでソート時には全要素がheapに入り、ソート後の追加は既存の部分の後ろに残る。

次は独自の短い操作列である。queueは先頭からの順、heapは内容を読みやすく昇順に記す。heapの内部配列の配置ではない。「移動」は今回queueからheapへ移した個数で、∅は空を表す。

操作queueheap移動
3, 1を順に追加3, 1∅0
ソート∅1, 32
0を追加01, 30
1を出力030
ソート∅0, 31
もう一度ソート∅0, 30
0, 3を順に出力∅∅0
2を追加・出力∅∅0
ソート∅∅0

0を追加した直後も先頭はheapの1であり、二つの容器の最小値を比較して0を先に出してはいけない。また、既にheapにある3は次のソートでも移動しない。最後に追加した2のように、queueから直接出力される要素は移動を一度も経験しない。

各ソートでのwhileの反復を、そこでheapへ移した要素に課金する。各要素の経路は「queue→heap→削除」または「queue→削除」であり、heapからqueueへ戻る経路はない。したがって全ソートでの反復数は追加要素数以下となる。表でも追加4個に対して移動は合計3回である。同じ値を複数回追加しても、それぞれ別の要素として数える。

削除した辺の再追加は、新しい実体として数える

ABC302 E「Isolation」では、空の無向グラフへ辺を追加する操作と、指定頂点につながる全辺を削除する操作がある。追加の直前にその辺は存在しないが、削除後に同じ端点対を再び追加することはできる。

各頂点の隣接先をsetで持ち、辺の追加時は両端の集合へ相手を入れる。頂点の全辺削除では、その頂点の隣接先を一つずつ列挙して相手側の集合からも消し、最後に自分側を空にする。両側から消すことで、後から反対側の頂点を処理しても同じ辺は再び列挙されない。

3頂点の例で、追加されるたびに辺へ新しい名前を付ける。

操作操作後に存在する辺今回の削除辺数
(1, 2)を追加e₁=(1, 2)0
(1, 3)を追加e₁, e₂=(1, 3)0
頂点1の全辺を削除∅2
頂点1の全辺を削除∅0
(1, 2)を再追加e₃=(1, 2)0
頂点2の全辺を削除∅1
頂点1の全辺を削除∅0

端点対は2種類だが、削除辺数の合計は3である。「同じ端点対は一度しか消さない」と数えると誤る。課金先は追加一回で生まれ、削除されるまで存在する辺の実体である。e₁とe₃は別実体なので、全辺削除の内側の反復数は辺の追加回数以下となる。無向辺を二つの隣接集合から消す費用は、一実体につき定数回の集合操作として数える。

孤立頂点数も、次数が0から正になる追加時、正から0になる削除時だけ更新すればよい。既に孤立している頂点の全辺削除では、反復も個数の変更も起きない。

成立条件と計算量

操作数を QQ、追加された要素・辺の実体数を RR とする。各実体が高々一度だけ内側の反復を起こすと証明できれば、総反復数は RR 以下である。一反復の費用の上界を TT とし、各操作の固定費用が定数なら、初期化を除く全体は O(Q+RT)O(Q+RT) 時間で抑えられる。反復しない空の操作も QQ の項へ含める。

ABC217 Eでは R≤QR\leq Q で、queue操作を定数時間、heapの挿入・取り出しを O(log⁡(Q+1))O(\log(Q+1)) 時間で行う。取り出し回数も QQ 以下なので、全体は O(Qlog⁡(Q+1))O(Q\log(Q+1)) 時間、空間は O(Q)O(Q) である。queueの先頭削除で残り全要素をずらす実装では、この評価にならない。

ABC302 Eでは頂点数を NN とすると、平衡木のset操作は O(log⁡(N+1))O(\log(N+1)) 時間である。追加ごとの挿入も定数回、削除時の総列挙も R≤QR\leq Q 回なので、集合を頂点ごとに用意する初期化と各操作後の出力を含め、全体は O(N+Qlog⁡(N+1))O(N+Q\log(N+1)) 時間、空間は O(N+Q)O(N+Q) となる。集合を空にする費用も、消す隣接要素の総数へ含める。

残りの処理予算を数値で持つ見方もできる。この値を**ポテンシャル(potential)**と呼ぶ。例えば未移動のqueue要素数なら、追加一回で1増え、移動一回で1減り、常に非負である。queueから直接出力する場合も1減るので、総移動数は初期量と全追加による増加量の和を超えない。部分問題サイズが半減する場合も、「あと何回半減できるか」という対数の予算を考えられる。

ただし、削除後に状態を巻き戻すrollbackがあると、この予算は復活する。例えば KK 個の要素を持つ状態へ戻すたびに全削除すれば、これを LL 回繰り返す総取り出し回数は KLKL になる。最初の KK 個だけに一度ずつ課金することはできない。復元・再生成で増える予算と、その操作自体の費用を数え直す必要がある。新たな実体や予算の生成数を入力サイズから抑えられることまで確認して使う。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。一度だけの削除やpotentialの減少に課金し、操作列全体を評価する。

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

概念上の親: 軽重分類と償却解析で総仕事量を抑える。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-amortized-monotone-progress

単調進行による償却解析

習得する技能

  • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

前提と範囲

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

直接の前提単元: なし。

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

要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 単調進行による償却解析の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠