考察
この問題では、一つの補助頂点が連続する番号の頂点すべてに、同じ重みの辺でつながる。軽い辺から接続していくと、元頂点の連結成分は連続区間にまとまる。そのため、どの頂点対が連結かを個別に管理する代わりに、隣り合う元頂点の間に残る「成分の境界」を管理すればよい。
元頂点を 、操作 で使う補助頂点を とする。この補助頂点から区間 の各元頂点へ、重み の辺がある。全辺を生成して通常のKruskal法を行うと、辺数は最大 本に達する。そこで、同じ補助頂点から出る辺を一まとまりとして、何本採用するかだけを求めることを考える。
まず操作を重み の昇順に並べる。同じ操作の辺はすべて同じ重みなので、Kruskal法ではそれらを続けて調べてよい。また、未処理の補助頂点に接する辺はその操作の辺だけなので、処理を始める直前の補助頂点は必ず孤立している。
ここで、一つの操作を終えるたびに、各連結成分に含まれる元頂点の集合が連続区間になることに注目する。初期状態は という単点区間である。区間 の補助頂点を処理すると、その区間と交わる旧成分をすべて一つに接続できる。交わる成分は途中を飛ばさずに並んでいるため、それらを丸ごと併合しても連続区間のままである。連続性をいうのは元頂点の番号についてであり、補助頂点の番号まで連続する必要はない。
元頂点 と の間を境界 と呼び、両者が別成分である境界だけを集合 に残す。成分が連続区間だからこそ、これらの境界で元頂点列を区切れば全成分を復元できる。操作 の内部に残っている境界数を とすると、区間内を左から見て境界を越えるたびに別の旧成分へ移るので、交わる旧成分は 個である。孤立した補助頂点から各成分へ一辺ずつ採用し、同じ成分への残りの辺は採用しない。よって、この操作の費用寄与は
となる。最初の一辺は補助頂点自身を接続するためのもので、境界を消すための 本とは別に必要である。
独自の小例として、、重み順の操作を とする。各組は を表す。初めは元頂点が一つずつ孤立しており、最初の操作で元頂点の成分は になる。境界集合と費用の変化を追うと、次のようになる。費用の式の括弧内は である。
二つ目の区間は頂点 から始まるが、すでに同じ成分の頂点 も含めて併合され、元頂点の成分は となる。最後の操作では元頂点の成分も境界集合も変わらないが、新しい補助頂点を接ぐ一辺は必要である。合計は となる。
残る課題は、区間内の未接続境界だけを速く探すことである。順序付き集合(ordered set)なら、指定した位置以上の最小の境界を lower_bound で取得でき、消した境界を次の操作で探し直さずに済む。具体的な手順は次のとおり。
- 操作を の昇順に並べ、、答えの累計を とする。
- 各操作 で
S.lower_bound(L) から始め、集合の末尾に達するか境界が 以上になるまで、境界を削除して進む。削除数を とし、答えに を加える。
- 全操作の後、 が空なら累計を出力し、残っていれば を出力する。
境界は一度消えたら再び現れないため、各操作で区間内の全頂点を走査せず、全体で高々 個の境界を削除するだけで済む。
典型の発動条件
implicit graphのKruskal
発動条件: 規則によって大量の辺が暗黙に与えられ、同じ重みの辺をまとめて処理できる最小全域木問題。
その重みの辺でどの成分が併合されるかを求め、Kruskal法の採用辺数を数える。辺を省略するには、成分の変化と費用が通常のKruskal法に一致する理由が必要になる。
削除型ordered set走査
発動条件: 多数の区間内にある未処理位置を列挙し、処理後は永久に不要になるとき。
lower_bound で未処理位置へ直接進み、列挙した位置を削除する。削除が一度限りであることから、区間数と区間長の積ではなく、最初の要素数で総列挙回数を抑えられる。
問題固有の要素
補助頂点の接続先が連続区間であるため、元頂点の成分も連続区間を保ち、一般の連結成分管理を 個の境界へ置き換えられる。任意の頂点集合へ接続する問題では、例えば だけが同じ成分になると隣接境界からその成分を復元できないので、この置き換えは使えない。
別の問題へ持ち帰る視点: 順序を持つ点群の成分をまとめる操作では、その順序上で成分の形が保たれるかを調べる。保たれるなら、全頂点対の関係よりも成分間の境界を追う。
正当性
各補助頂点の処理を終えた時点で、元頂点を含む連結成分の元頂点集合は連続区間であり、集合 は成分間の境界を過不足なく表すことを示す。初期状態では各元頂点が単独の区間で、すべての境界が に入っているので成り立つ。
次に区間 の補助頂点を処理する。処理前の成分は連続区間なので、この区間と交わる成分は左から連続して並び、その間の境界はちょうど にある の位置である。その数が なら交わる成分は 個ある。両端の成分が の外まで延びていても、交わる成分を丸ごと併合した元頂点集合は一つの連続区間になる。交わらない成分は変わらず、成分間でなくなる境界も列挙した 個だけなので、不変条件が保たれる。
現在の補助頂点に接する辺は今まで一本も処理しておらず、この頂点は孤立している。区間内の頂点への辺を左から調べれば、最初の旧成分への一辺を採用し、その成分内の残りの辺は閉路を作るため棄却する。次の旧成分へ進むたびに一辺を採用するので、採用する辺はちょうど 本となる。したがって境界の削除と の加算は、実際の辺にKruskal法を適用した結果と一致する。重みを昇順に処理しているため、得られる森は最小全域森である。同じ重みの辺はどの順で調べてもよいので、同重みの区間も任意の順に一つずつ処理できる。
最後に が空ならすべての元頂点が一つの成分に属する。各補助頂点も処理時に少なくとも一辺を採用して元頂点へ接続済みなので、全 頂点が連結であり、求めた費用が最小全域木の費用である。境界が残れば元頂点の成分が複数あり、全候補辺を処理しても接続できなかったことから元のグラフも非連結で、答えは となる。
実装上の注意
- 境界 は元頂点 の間を表す。削除対象は であり、 自身は消さない。C++の
std::set では、末尾の判定をしてから値を参照し、it = S.erase(it) として削除後の次の要素へ進む。
- なら区間内の境界はなく、 である。すでに区間内の全頂点が同じ成分になっている場合や、同じ区間が重複する場合も、新しい補助頂点の分として必ず を加える。
- では初めから が空である。それでも全操作を処理し、各補助頂点を唯一の元頂点につなぐ費用 を求める。途中で集合が空になっても処理を打ち切らない。
- 同じ重みの操作は任意の順に処理でき、まとめてから境界を更新する必要はない。
- 費用の上限は なので、積の計算前から64 bit整数を使う。
復習の核
- 成分の代表を管理する前に、成分が区間などの単純な形を保つかを調べる。隣接境界だけでよい根拠は、この不変条件にある。
- 消えた境界数は「旧成分同士をつなぐための追加分」である。毎回増える補助頂点自身の一辺を忘れず、 でも費用を加える。
- 区間を何度も走査しそうなとき、処理済み位置を永久に除けるなら、区間長の総和ではなく各位置が処理される回数で見積もる。
計算量と制約
時間
操作のソートに 、境界集合の初期化に 。各操作で一回行う lower_bound は全体で 、境界の削除は全体で高々 回なので、各削除を と評価しても合計 である。したがって全体は
となる。 としているのは、境界がない でも各操作に定数時間が必要なことを含めるためである。
空間
境界集合に高々 要素、操作列に 要素を保持するので、全体で 。
制約との対応
公式制約は 、、 で、入力はすべて整数である。制限時間は2秒、メモリ制限は1024 MiB。最大 本の辺は生成せず、入力のソートと各境界一度限りの削除に抑えることで、この制約に対応する。
出典