ABC 264 E — Blackout 2

考察

切れた電線を順に処理すると、連結成分が分裂して管理しにくい。切断予定はすべて分かっているので、全切断後から電線を逆順に戻そう。すると必要なのは成分の併合だけになる。さらに、どの発電所へ届くかは問われないため、発電所を一つの代表頂点へまとめると、その成分の大きさから通電都市数が分かる。

毎回の探索で、何を繰り返しているか

都市が NN 個、発電所が MM 個あり、電線を指定順に一本ずつ切る。都市からどれかの発電所へ到達できれば、その都市は通電している。各切断の直後の通電都市数を求める。

毎回、全発電所からBFSやDFSで到達都市を数えれば正しい。しかし切断が最大50万回もあり、毎回グラフ全体を調べる O(Q(N+M+E))O(Q(N+M+E)) 時間では足りない。連結成分を更新して使い回したい。

Union-Find(DSU)は二成分をまとめるのは得意だが、普通のDSUは一成分を分けられない。電線が一本切れても、迂回路があれば成分は変わらず、なければ分裂する。切断をDSUの親子関係から直接取り除くこともできない。親子関係は、元の電線をそのまま保存しているわけではないからだ。

ここで、操作がすべて事前に分かることを使う。最後まで切れない電線だけで最終グラフを作り、切った電線を最後のものから戻す。逆向きには成分が分かれず、辺の追加による併合だけになる。

答えを記録するのは、電線を戻す前

都市1〜4、発電所P、Qを持つ独自例を考える。電線は次の五本である。

1 ─ 2 ─ P
    │
    3 ─ 4 ─ Q

2 ⁣− ⁣32\! -\! 3、4 ⁣− ⁣Q4\! -\! Q、2 ⁣− ⁣P2\! -\! P の順に切ると、通電都市数は4、2、0になる。全切断後には都市の辺 1 ⁣− ⁣21\! -\! 2 と 3 ⁣− ⁣43\! -\! 4 だけが残る。

逆向きに今から戻す電線戻す前の通電数戻した後の通電数
2 ⁣− ⁣P2\! -\! P02
4 ⁣− ⁣Q4\! -\! Q24
2 ⁣− ⁣32\! -\! 344

必要なのは各行の「戻す前」であり、これを元の順に並べれば4、2、0になる。戻した後を保存すると、一つ前の時刻の答えを記録してしまう。

切断を ii 回行った後のグラフを GiG_i と呼び、切る電線の番号を XiX_i とする。逆走査では、辺 XiX_i を戻す直前の状態が GiG_i、直後が Gi−1G_{i-1} である。この対応を先に定めれば、記録のタイミングを迷わず決められる。

「どれかに届く」を、一つの頂点への到達へ変える

逆向きの併合ができても、発電所は複数ある。都市は一個でも発電所に届けばよく、発電所の名前や個数は答えに使わない。この点を利用し、すべての発電所を特殊頂点 ss 一個へ置き換える。

都市の番号はそのまま残す。電線の端点が発電所なら ss へ写し、都市なら元の都市へ写す。発電所間の電線は自己ループになるが、連結成分を変えないので併合時に無視してよい。こうして N+1N+1 頂点のDSUを使う。

変換により、もともと別の発電所につながっていた都市も一成分になる。たとえば 1 ⁣− ⁣P1\! -\! P と 2 ⁣− ⁣Q2\! -\! Q しかなくても、変換後は 1 ⁣− ⁣s ⁣− ⁣21\! -\! s\! -\! 2 とつながる。都市同士の連結関係は変わるが、通電している都市の集合は変わらない。

なぜ通電判定は変わらないのか。元の発電所への経路は、その発電所を ss へ写せば変換後の経路になる。逆に、都市から ss に初めて着くまでの経路では、中間はすべて都市であり、最後の辺は元のどれかの発電所への電線だった。その部分を戻せば元のグラフにも通電経路がある。

従って通電都市数は、

size⁡(s)−1\operatorname{size}(s)-1

で得られる。ss の成分に発電所の代表自身が一個含まれるので、それを引く。

全切断後から、辺を一本ずつ復元する

まず電線を番号付きで保存し、切断対象の番号に印を付ける。NN 都市と特殊頂点 ss を単独成分で初期化し、印のない電線をすべて併合する。これで全切断後のグラフができる。

次に i=Q,Q−1,…,1i=Q,Q-1,\ldots,1 の順で、以下を行う。

  1. size⁡(s)−1\operatorname{size}(s)-1 を回答配列の ii 番目へ保存する。
  2. 電線 XiX_i の両端を変換後の頂点へ写し、DSUで併合する。

最後に回答配列を先頭から出力する。同じ成分内への辺の追加は、サイズを変えない。切断対象はすべて相異なるので、一つの印と一回の復旧で十分である。

典型の発動条件

更新の向きを変え、使えるデータ構造を変える

逆順処理を候補にするのは、全操作が事前に分かり、順方向の操作に対して、逆方向の操作を速く扱える場合である。本問では「削除で分裂する」が「追加で併合する」へ変わり、DSUが使える。

大切なのは、逆関数をそのまま実行することではない。削除後の最終グラフを作り、必要な元の各時点を逆順に再現している。上書きのように元の値を失う操作でも、逆から見て最後に有効な操作を確定する方法がある。逆向きに何が単調になるかを探すとよい。

全質問が分かるだけでは十分でない。辺の追加と削除が混在すると、逆にしても両方が残り、通常のDSUだけでは解けない。終状態を構築できるかと、逆操作が本当に簡単になるかをセットで確認する。

問いに必要な区別だけをグラフへ残す

「どれかの特殊頂点へ到達できるか」だけが必要なら、特殊頂点を一つへまとめることを検討できる。本問ではこの変換が通電判定を保つため、属性の集計をサイズ取得へ落とせた。ただし都市同士の連結や到達先の種類まで保つ変換ではない。

それらの区別が必要なら、元の頂点を残し、成分へ属性を持たせる。本問でも、成分内の都市数 cc と発電所有無 pp を持つ方法で解ける。異なる二成分を併合するとき、片方だけ pp が真なら、偽の側の都市数だけ通電数が増える。両方真ならどちらも既に通電し、両方偽ならまだ通電しないので増分0である。属性は都市数の和と発電所有無の論理和で更新する。

縮約で区別を消す方法と、成分へ属性を足す方法は、必要な問いから選ぶ。本問の主解法では、答えに不要な発電所ごとの区別を消すことで処理を簡潔にした。

問題固有の要素

本問は発電所を「少なくとも一つ」含む成分の都市数だけを問う。この存在判定が、全発電所を一頂点へまとめる根拠である。「何個の発電所へ届くか」「特定の発電所へ届くか」なら同じ変換は使えない。問題文の量化、特に「どれか」と「すべて」の違いを読むことが、モデルを簡単にする手がかりになる。

正当性

各時点で、元のグラフの都市から発電所へ至る経路は、発電所を ss へ写すことで変換後の経路になる。逆に変換後の都市から ss への経路を、最初に ss へ到達するまで取れば、最後の辺を元の発電所への電線に戻せる。途中の都市間の辺も元のグラフに存在する。従って変換前後で通電都市は一致する。

切断されない辺だけを併合した初期DSUは、変換後の GQG_Q の連結成分を表す。辺 XiX_i を戻す直前に GiG_i の成分を表しているなら、その時点の ss の成分サイズから1を引いた値が切断 ii の直後の答えである。辺を戻して両端を併合すると、ちょうど Gi−1G_{i-1} の成分になる。

この対応を i=Qi=Q から1まで繰り返せるため、すべての回答は正しい。元の順に出力することで、要求された各切断直後の値が得られる。

実装上の注意

  • 電線の端点の組ではなく、入力で付いた電線番号で切断を管理する。縮約後は別々の電線が同じ二頂点を結ぶ場合がある。
  • 特殊頂点のサイズを取得するときは、現在の根を経由する。併合で ss 自身が根でなくなっても、答えはその成分のサイズである。
  • 発電所間の辺や同じ成分内の辺を加えても、成分サイズを二重に足さない。DSUの通常の同根判定を使う。
  • 逆走査では必ず記録してから復旧する。答えを逆順に蓄積する実装なら、出力前に反転する。

復習の核

  • 削除が難しければ、全削除後を作って追加だけにできないか調べる。
  • 逆順では「今が元の何回目の操作の前後か」を定義してから回答を保存する。
  • 特殊頂点の区別を消す前に、保存したい問いの双方向の対応を確認する。
  • DSUに足す属性は問いに合わせる。存在だけなら真偽、個数なら個数を持つ。

計算量と制約

時間

発電所を端点の読込時に特殊頂点へ写し、DSUを N+1N+1 頂点で用意する。切断対象の印付けと電線の走査に O(E+Q)O(E+Q)、初期化・全復旧で合計高々 EE 回の併合を行う。経路圧縮とサイズによる併合を使えば、全体で O(N+Eα(N+1)+Q)O(N+E\alpha(N+1)+Q) 時間。α\alpha は逆Ackermann関数で、成分サイズの取得も根探索の償却時間に含める。

空間

DSUに O(N)O(N)、電線一覧と印に O(E)O(E)、切断順と回答に O(Q)O(Q)。入力を含め全体で O(N+E+Q)O(N+E+Q) 空間となる。元の全頂点にDSUを用意する成分属性版なら、これに O(M)O(M) も含む。

制約との対応

N+M≤2×105N+M\leq2\times10^5、Q≤E≤5×105Q\leq E\leq5\times10^5。切断番号は相異なり、全操作が入力で先に得られる。逆順化によって各電線を高々一回追加する処理へ変え、この大きさに対応する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Blackout 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

主題
追加で学ぶ技能
    なし
    既習技能
    • DSUによる連結成分管理・縮約: 成分へmetadataまたはmerge履歴を集約し、成分を一頂点に縮約した隣接関係、または併合後の代表情報を構成できる。

    主タグ: 逆向きのオフライン処理

    補助タグ: DSUによる連結成分管理・縮約

    執筆: abc-explanation-author1.1.1 / revision 4

    学習の位置

    体系上の位置: 時間を逆向きにして未来依存を消す

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

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

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

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題