時間を逆向きにして未来依存を消す

概要

削除の後に何が残るか、何度も上書きした後にどの値が生きるか。順方向には面倒な更新でも、全操作を先に読めるなら、後ろから処理すると単純になることがある。削除は追加へ、最後の上書きは最初の確定へ変わる。

逆向きのオフライン処理では、過去の状態をすべて保存する代わりに、必要な情報が確定する向きから操作列を読む。逆順にするだけで速くなるわけではない。どの操作が簡単になり、何を保持すれば元の各時点の答えへ戻せるかを設計するのが、この単元の目的である。

考え方

一方向にだけ難しい操作を見つける

連結したグラフから辺を一本消す場面を考える。その辺に迂回路があれば何も変わらず、なければ一成分が二つに分かれる。普通のDSUは成分の統合を表すので、既にまとめた成分を分ける処理はできない。

辺の切断予定がすべて分かっていれば、切断されない辺だけを最初に用意できる。そこへ最後に切った辺から順に戻すと、必要なのは二頂点の成分を併合する操作だけになる。DSUが扱えない操作を高度な構造で直接解こうとする前に、既知の操作列を逆向きに読む選択肢を検討できる。

ABC264 Eは、この追加だけのグラフで発電所へ到達する都市数を求める問題である。逆順化の後に何を集計するかは別途設計し、発電所を一頂点へまとめるか、成分へ都市数と発電所有無を持たせる。

時刻の対応を決めてから、答えを保存する

一般に、初期状態を G0G_0、操作 ii が終わった状態を GiG_i と呼ぶ。操作は 1,…,Q1,\ldots,Q の順で行われるとする。

辺削除を戻す逆走査では、初期化で GQG_Q を作る。逆操作 ii の直前が GiG_i、直後が Gi−1G_{i-1} である。

順方向で欲しいもの逆方向で記録する時点
操作 ii の直後の答え操作 ii を戻す前
操作 ii の直前の答え操作 ii を戻した後

例えば一本の道 1 ⁣− ⁣2 ⁣− ⁣31\! -\! 2\! -\! 3 で、辺 1 ⁣− ⁣21\! -\! 2、2 ⁣− ⁣32\! -\! 3 を順に消すと、連結成分数は2、3になる。逆順では孤立三頂点から始め、3を記録して辺 2 ⁣− ⁣32\! -\! 3 を戻し、2を記録して辺 1 ⁣− ⁣21\! -\! 2 を戻す。記録を元の順へ戻せば2、3である。

記録を「逆操作の後」にすると2、1を拾ってしまう。逆順化の典型的な実装ミスは、この一時点のずれである。ループの先頭で、保持状態が元の何時点を表すかを定義すると防げる。

頂点削除を戻す場合は、頂点が再び有効になる操作も必要になる。まずその頂点を一成分として追加し、有効な隣接頂点とだけ併合する。一つの辺を何度処理するかと、まだ無効な頂点を数えていないかまで確認する。

上書きは、後から読むと一度だけ確定する

逆操作を計算できない更新もある。行全体を赤で塗った後では、以前の色を一般には復元できない。しかし最終盤面だけが必要なら、前の色を復元する必要そのものがない。

2行3列の盤面へ、次を順に行うとする。初期色を白とする。

  1. 一行目を赤にする。
  2. 二列目を青にする。
  3. 一行目を緑にする。

最終的には一行目の三マスが緑、二行二列目が青、残る二マスが白になる。各マスの最終色を決めるのは、そのマスに作用した最後の操作だけだ。

逆順に読み、既に最終色の決まった行・列を記録する。操作3の一行目は未確定の三マスを緑へ確定する。操作2の二列目では一行目は確定済みなので、残る一マスだけを青へ確定する。操作1の一行目は既に見た行なので寄与しない。

一般に、未処理の行を初めて見たら、その行でまだ未確定なのは「全列数−既に処理した列数」マスである。未処理の列なら「全行数−既に処理した行数」マスとなる。その数だけ色へ加算し、行または列を処理済みにする。全操作を読んだ後、未確定行数と未確定列数の積が、初期色のまま残るマス数になる。

この処理では過去の盤面を再現していない。必要な最終情報を、後勝ちの優先順位で一度ずつ確定している。ABC346 Eへ進む際は、この一マス一回の対応から計数式を導くとよい。

挿入順の復元は、完成後の空き場所から考えられる

列の途中へ一要素ずつ挿入すると、既存要素の位置がずれる。完成形を直接更新する代わりに、最後に挿入したものから、その置き場所を確定する方法がある。

A を一番目、B を一番目、C を二番目へ順に挿入すると、列は A、BA、BCA と変わる。完成後の三つの場所を空きとして用意し、逆から処理する。

置く要素空き場所選ぶ場所
C1、2、3二番目の空き=2
B1、3一番目の空き=1
A3一番目の空き=3

後から挿入された要素を既に置いた状態では、残る空き場所の相対順が、今回の挿入直後の列の順序に対応する。そのため、指定された挿入順位と同じ順位の空きを選べばよい。空き場所に1、埋まった場所に0を置き、Fenwick Treeなどで「左から何個目の1か」を求めると、一回 O(log⁡N)O(\log N) で配置できる。ABC392 Fはこの見方を使う。

逆順が解消する困難を、具体的に言葉にする

以上の例では、それぞれ違う量が扱いやすくなった。

  • 辺削除:成分を分ける代わりに、併合だけ行う。
  • 上書き:何度も値を変える代わりに、最終値を一度だけ確定する。
  • 途中挿入:既存要素をずらす代わりに、空き場所を一つずつ埋める。

この違いから必要な道具も変わる。DSU、処理済みフラグ、順位を探す木を、操作の向きだけで一律に選ばない。

また、逆から読めば常に単調になるわけではない。追加と削除が混在すれば逆順でも混在する。全操作後の状態を作れない場合や、今回の答えで次の入力が決まる対話的な処理でも、この方法をそのまま適用できない。値順で並べるsweepは、時間を反転することとは別の順序設計である。

成立条件と計算量

適用前に、全操作・質問を先に得られること、開始に必要な終状態または未確定状態を作れること、逆向きの一操作を必要な情報だけで処理できることを確認する。順方向の各時点を再現する方法なら時刻の対応、最終情報だけを確定する方法なら一対象が何回数えられるかを正当化する。

逆順に読むこと自体は QQ 操作で O(Q)O(Q)。高速化できるかは、変換後の各操作の費用と処理回数で決まる。辺削除のみの連結性では、VV 頂点・EE 辺に対して初期化と復旧で各辺を高々一回併合し、O(V+(E+Q)α(V))O(V+(E+Q)\alpha(V)) 時間、辺・操作・回答を含め O(V+E+Q)O(V+E+Q) 空間となる。

行・列の上書きでは、各操作を一回読み、各行・列を高々一回確定する。色を配列で直接集計できるなら O(H+W+Q+C)O(H+W+Q+C) 時間・空間で、CC は色配列の大きさである。色の種類が疎なら辞書を使い、その操作費用と出力する色の並べ替えも加える。盤面 HWHW マスを作る必要はないが、マス数の積は64 bit整数で計算する。

挿入順位からの復元は、空き場所の初期化と NN 回の順位探索・削除に O(Nlog⁡N)O(N\log N) 時間・O(N)O(N) 空間。逆順化は候補を減らす視点であり、計算量は接続するデータ構造まで含めて評価する。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。削除を追加に変えるなど、時間を逆に読むことで扱える操作を増やす。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-reverse-offline

習得する技能

  • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

前提と範囲

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

直接の前提単元: なし。

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

削除・上書き・未来依存を含む更新列を逆向きに読み、追加だけ・first-writeだけなどの単調な処理へ変換して元の時刻へ答えを戻す。

このUnitでは扱わないもの

  • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

根拠