ABC 364 F — Range Connect MST

考察

この問題では、一つの補助頂点が連続する番号の頂点すべてに、同じ重みの辺でつながる。軽い辺から接続していくと、元頂点の連結成分は連続区間にまとまる。そのため、どの頂点対が連結かを個別に管理する代わりに、隣り合う元頂点の間に残る「成分の境界」を管理すればよい。

元頂点を 1,…,N1,\ldots,N、操作 ii で使う補助頂点を N+iN+i とする。この補助頂点から区間 [Li,Ri][L_i,R_i] の各元頂点へ、重み CiC_i の辺がある。全辺を生成して通常のKruskal法を行うと、辺数は最大 NQNQ 本に達する。そこで、同じ補助頂点から出る辺を一まとまりとして、何本採用するかだけを求めることを考える。

まず操作を重み CiC_i の昇順に並べる。同じ操作の辺はすべて同じ重みなので、Kruskal法ではそれらを続けて調べてよい。また、未処理の補助頂点に接する辺はその操作の辺だけなので、処理を始める直前の補助頂点は必ず孤立している。

ここで、一つの操作を終えるたびに、各連結成分に含まれる元頂点の集合が連続区間になることに注目する。初期状態は [1,1],[2,2],…,[N,N][1,1],[2,2],\ldots,[N,N] という単点区間である。区間 [L,R][L,R] の補助頂点を処理すると、その区間と交わる旧成分をすべて一つに接続できる。交わる成分は途中を飛ばさずに並んでいるため、それらを丸ごと併合しても連続区間のままである。連続性をいうのは元頂点の番号についてであり、補助頂点の番号まで連続する必要はない。

元頂点 jj と j+1j+1 の間を境界 jj と呼び、両者が別成分である境界だけを集合 SS に残す。成分が連続区間だからこそ、これらの境界で元頂点列を区切れば全成分を復元できる。操作 [L,R][L,R] の内部に残っている境界数を kk とすると、区間内を左から見て境界を越えるたびに別の旧成分へ移るので、交わる旧成分は k+1k+1 個である。孤立した補助頂点から各成分へ一辺ずつ採用し、同じ成分への残りの辺は採用しない。よって、この操作の費用寄与は

(k+1)C(k+1)C

となる。最初の一辺は補助頂点自身を接続するためのもので、境界を消すための kk 本とは別に必要である。

独自の小例として、N=4N=4、重み順の操作を (1,2,2),(2,4,5),(3,3,7)(1,2,2),(2,4,5),(3,3,7) とする。各組は (L,R,C)(L,R,C) を表す。初めは元頂点が一つずつ孤立しており、最初の操作で元頂点の成分は [1,2],[3,3],[4,4][1,2],[3,3],[4,4] になる。境界集合と費用の変化を追うと、次のようになる。費用の式の括弧内は k+1k+1 である。

処理した操作残る境界集合 SS費用寄与
初期状態{1,2,3}\{1,2,3\}—
(1,2,2)(1,2,2){2,3}\{2,3\}(1+1)×2=4(1+1)\times2=4
(2,4,5)(2,4,5)∅\varnothing(2+1)×5=15(2+1)\times5=15
(3,3,7)(3,3,7)∅\varnothing(0+1)×7=7(0+1)\times7=7

二つ目の区間は頂点 22 から始まるが、すでに同じ成分の頂点 11 も含めて併合され、元頂点の成分は [1,4][1,4] となる。最後の操作では元頂点の成分も境界集合も変わらないが、新しい補助頂点を接ぐ一辺は必要である。合計は 4+15+7=264+15+7=26 となる。

残る課題は、区間内の未接続境界だけを速く探すことである。順序付き集合(ordered set)なら、指定した位置以上の最小の境界を lower_bound で取得でき、消した境界を次の操作で探し直さずに済む。具体的な手順は次のとおり。

  1. 操作を CiC_i の昇順に並べ、S={1,…,N−1}S=\{1,\ldots,N-1\}、答えの累計を 00 とする。
  2. 各操作 (L,R,C)(L,R,C) で S.lower_bound(L) から始め、集合の末尾に達するか境界が RR 以上になるまで、境界を削除して進む。削除数を kk とし、答えに (k+1)C(k+1)C を加える。
  3. 全操作の後、SS が空なら累計を出力し、残っていれば −1-1 を出力する。

境界は一度消えたら再び現れないため、各操作で区間内の全頂点を走査せず、全体で高々 N−1N-1 個の境界を削除するだけで済む。

典型の発動条件

implicit graphのKruskal

発動条件: 規則によって大量の辺が暗黙に与えられ、同じ重みの辺をまとめて処理できる最小全域木問題。

その重みの辺でどの成分が併合されるかを求め、Kruskal法の採用辺数を数える。辺を省略するには、成分の変化と費用が通常のKruskal法に一致する理由が必要になる。

削除型ordered set走査

発動条件: 多数の区間内にある未処理位置を列挙し、処理後は永久に不要になるとき。

lower_bound で未処理位置へ直接進み、列挙した位置を削除する。削除が一度限りであることから、区間数と区間長の積ではなく、最初の要素数で総列挙回数を抑えられる。

問題固有の要素

補助頂点の接続先が連続区間であるため、元頂点の成分も連続区間を保ち、一般の連結成分管理を N−1N-1 個の境界へ置き換えられる。任意の頂点集合へ接続する問題では、例えば {1,3}\{1,3\} だけが同じ成分になると隣接境界からその成分を復元できないので、この置き換えは使えない。

別の問題へ持ち帰る視点: 順序を持つ点群の成分をまとめる操作では、その順序上で成分の形が保たれるかを調べる。保たれるなら、全頂点対の関係よりも成分間の境界を追う。

正当性

各補助頂点の処理を終えた時点で、元頂点を含む連結成分の元頂点集合は連続区間であり、集合 SS は成分間の境界を過不足なく表すことを示す。初期状態では各元頂点が単独の区間で、すべての境界が SS に入っているので成り立つ。

次に区間 [L,R][L,R] の補助頂点を処理する。処理前の成分は連続区間なので、この区間と交わる成分は左から連続して並び、その間の境界はちょうど SS にある L≤j<RL\leq j<R の位置である。その数が kk なら交わる成分は k+1k+1 個ある。両端の成分が [L,R][L,R] の外まで延びていても、交わる成分を丸ごと併合した元頂点集合は一つの連続区間になる。交わらない成分は変わらず、成分間でなくなる境界も列挙した kk 個だけなので、不変条件が保たれる。

現在の補助頂点に接する辺は今まで一本も処理しておらず、この頂点は孤立している。区間内の頂点への辺を左から調べれば、最初の旧成分への一辺を採用し、その成分内の残りの辺は閉路を作るため棄却する。次の旧成分へ進むたびに一辺を採用するので、採用する辺はちょうど k+1k+1 本となる。したがって境界の削除と (k+1)C(k+1)C の加算は、実際の辺にKruskal法を適用した結果と一致する。重みを昇順に処理しているため、得られる森は最小全域森である。同じ重みの辺はどの順で調べてもよいので、同重みの区間も任意の順に一つずつ処理できる。

最後に SS が空ならすべての元頂点が一つの成分に属する。各補助頂点も処理時に少なくとも一辺を採用して元頂点へ接続済みなので、全 N+QN+Q 頂点が連結であり、求めた費用が最小全域木の費用である。境界が残れば元頂点の成分が複数あり、全候補辺を処理しても接続できなかったことから元のグラフも非連結で、答えは −1-1 となる。

実装上の注意

  • 境界 jj は元頂点 j,j+1j,j+1 の間を表す。削除対象は L≤j<RL\leq j<R であり、RR 自身は消さない。C++の std::set では、末尾の判定をしてから値を参照し、it = S.erase(it) として削除後の次の要素へ進む。
  • L=RL=R なら区間内の境界はなく、k=0k=0 である。すでに区間内の全頂点が同じ成分になっている場合や、同じ区間が重複する場合も、新しい補助頂点の分として必ず CC を加える。
  • N=1N=1 では初めから SS が空である。それでも全操作を処理し、各補助頂点を唯一の元頂点につなぐ費用 ∑i=1QCi\sum_{i=1}^{Q}C_i を求める。途中で集合が空になっても処理を打ち切らない。
  • 同じ重みの操作は任意の順に処理でき、まとめてから境界を更新する必要はない。
  • 費用の上限は (N+Q−1)×109<4×1014(N+Q-1)\times10^9<4\times10^{14} なので、積の計算前から64 bit整数を使う。

復習の核

  • 成分の代表を管理する前に、成分が区間などの単純な形を保つかを調べる。隣接境界だけでよい根拠は、この不変条件にある。
  • 消えた境界数は「旧成分同士をつなぐための追加分」である。毎回増える補助頂点自身の一辺を忘れず、k=0k=0 でも費用を加える。
  • 区間を何度も走査しそうなとき、処理済み位置を永久に除けるなら、区間長の総和ではなく各位置が処理される回数で見積もる。

計算量と制約

時間

操作のソートに O(Qlog⁡Q)O(Q\log Q)、境界集合の初期化に O(Nlog⁡(N+1))O(N\log(N+1))。各操作で一回行う lower_bound は全体で O(Qlog⁡(N+1))O(Q\log(N+1))、境界の削除は全体で高々 N−1N-1 回なので、各削除を O(log⁡(N+1))O(\log(N+1)) と評価しても合計 O(Nlog⁡(N+1))O(N\log(N+1)) である。したがって全体は

O(Qlog⁡Q+(N+Q)log⁡(N+1))O(Q\log Q+(N+Q)\log(N+1))

となる。N+1N+1 としているのは、境界がない N=1N=1 でも各操作に定数時間が必要なことを含めるためである。

空間

境界集合に高々 N−1N-1 要素、操作列に QQ 要素を保持するので、全体で O(N+Q)O(N+Q)。

制約との対応

公式制約は 1≤N,Q≤2×1051\leq N,Q\leq2\times10^5、1≤Li≤Ri≤N1\leq L_i\leq R_i\leq N、1≤Ci≤1091\leq C_i\leq10^9 で、入力はすべて整数である。制限時間は2秒、メモリ制限は1024 MiB。最大 NQNQ 本の辺は生成せず、入力のソートと各境界一度限りの削除に抑えることで、この制約に対応する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Range Connect MST の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: cut・cycle性質から最適全域木を構成する

主題
追加で学ぶ技能
    なし
    既習技能
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
    • DSUによる連結成分管理・縮約: 静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 最小・最大全域木とcut・cycle性質

    補助タグ: 単調進行による償却解析 DSUによる連結成分管理・縮約 ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: cut・cycle性質から最適全域木を構成する

    • cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

    • 任意の全域木を一つ構成するだけの探索、および辺重みを最適化しない連結成分管理。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題