復興事業 解説
松尾 凜太朗 /QCFium

問題概要
辺に整数が書かれている無向グラフが与えられる。
以下の形のクエリを Q 個処理せよ :整数 x が与えられる。コスト 1 で辺に書かれている整数を 1 増減させることで、 x が書かれている辺のみで全頂点間を行き来できるようにするときの最小コストを求める

問題概要
辺に整数が書かれている無向グラフが与えられる。
以下の形のクエリを Q 個処理せよ :整数 x が与えられる。整数 c が書かれている辺のコストを |c - x|としたとき、グラフの最小全域木を求めるN ≦ 500
M ≦ 100000
Q ≦ 1000000

小課題 1M ≦ 16, Q ≦ 10
全域木に使う辺の集合を全探索 (2^M 通り )→ 本当に連結になっているならば使った辺についてコストを計算する
O(Q×2^M×M)クラスカル法
全ての辺を、コストの小さい順に見ていく
まだその辺が繋ぐ 2 点が連結でないならばその辺を追加する
既に連結ならばスキップする
最終的に追加された辺が最小全域木となる

辺の追加 & 連結判定 → UnionFindクラスカル法
全ての辺を、コストの小さい順に見ていく63458

クラスカル法
全ての辺を、コストの小さい順に見ていく
634538

クラスカル法
全ての辺を、コストの小さい順に見ていく
6345384

クラスカル法
全ての辺を、コストの小さい順に見ていく
63453485クラスカル法
全ての辺を、コストの小さい順に見ていく
63456384

クラスカル法
全ての辺を、コストの小さい順に見ていく
634563848

クラスカル法
全ての辺を、コストの小さい順に見ていく
63456384

クラスカル法 証明
なぜこれでよいのか
最小コストの辺を使わないのが最小だったとすると ...

34534885

最小コストの辺を使っても損をしないクラスカル法 証明
なぜこれでよいのか
最小コストの辺を使うことにしたので縮約して同じことを繰り返す→ クラスカル法と同じことをしている
634568548

小課題 2Q ≦ 10
各クエリで各辺のコストを普通に計算 → クラスカル法
O(QMlog(M))

小課題 3
1

3

220
103

小課題 3
1|x - 3|

3

220
103

小課題 3
1x<3→3–xx≧3→x-3

3

220
103

小課題 3
1x<3→3–xx≧3→x-3

3

220
103

コストは x の範囲ごとに x の 1 次関数

x ≦ 10 → 10 – x
10 ≦ x < 15 → x – 1015 ≦ x < 20 → 20 – x
20 ≦ x → x - 20

小課題 313220
103

1 次関数は変化する+ (2x - 6)x<3→3–xx≧3→x-3x ≦ 10 → 10 – x
10 ≦ x < 15 → x – 10
15 ≦ x < 20 → 20 – x
20 ≦ x → x - 20

小課題 3
最初 : 13 - 2x
x = 3 : +(2x - 6)
x = 10 : +(2x - 20)
x = 15 : +(-2x + 30)
x = 20 : +(2x - 40)

小課題 3
最初 : 13 - 2xx=1x = 3 : +(2x - 6)
x = 10 : +(2x - 20)
x = 15 : +(-2x + 30)
x = 20 : +(2x - 40)

小課題 3
最初 : 13 - 2xx = 3 : +(2x - 6)x=5x = 10 : +(2x - 20)
x = 15 : +(-2x + 30)
x = 20 : +(2x - 40)

小課題 3
最初 : 13 - 2x
x = 3 : +(2x - 6)
x = 10 : +(2x - 20)
x = 15 : +(-2x + 30)
x = 18x = 20 : +(2x - 40)

小課題 3
全体のコストの 1 次式が変化するタイミングを列挙 & ソート→ クエリを昇順に処理
O(Mlog(M) + Q)

小課題 4,5
小課題 4 : M ≦ 1000
小課題 5 : Q ≦ 20000
毎クエリ全ての辺のコストを計算していては間に合わない→ 視点を変える

小課題 4,5
小課題 4 : M ≦ 1000
小課題 5 : Q ≦ 20000
毎クエリ全ての辺のコストを計算していては間に合わない→ 視点を変える
ある辺がクラスカル法で使われる可能性があるのは x がどんな値のときか ?

考察
注目の辺

注目の辺よりコスト低

クエリ→ 注目の辺が頂点 a,b を繋いでいるとして、赤線だけで a,b が連結ならば注目の辺は使われない

考察
注目の辺

注目の辺よりコスト低

クエリ→ 注目の辺より右にある辺を順に追加していって a,b が連結になったら、そこより右にあるクエリでは注目の辺は使われない

考察
注目の辺

注目の辺よりコスト低

クエリ→ 注目の辺より右にある辺を順に追加していって a,b が連結になったら、そこより右にあるクエリでは注目の辺は使われない
左右で同じことをする

考察
各辺についてそれが使われる可能性のある x の範囲を求めるのを愚直にやって O(M^2α(N))
各クエリで絞った 2(N – 1) 本をソートしてクラスカル→ O(QNlog(N))
小課題 4 (M ≦ 1000) では QNlog(N), 小課題 5 (Q ≦ 20000) では M^2α(N) が大きすぎる小課題 5Q ≦ 20000
実は先ほどの解法はそのまま通る
クエリ側から使う可能性のある辺の数を考える

注目のクエリ小課題 5Q ≦ 20000
実は先ほどの解法はそのまま通る
クエリ側から使う可能性のある辺の数を考える

注目のクエリオレンジの範囲の辺で a,b が非連結 → オレンジの矢印の向きにクラスカ
ル法をすると注目の辺は使われる→ 各クエリ左右それぞれ N - 1 本以下

小課題 5同じ辺と辺の区間にあるクエリを同一視すると使われ得る辺とクエリの組は合計 O(MN) 個→ 実は先ほどの解法はそのまま通る (O(MNα(N) + QNlog(N))

クエリ

注目の辺

小課題 4M ≦ 1000
各クエリで 2(N – 1) 本の候補となる辺でクラスカル法を行う
部分 (O(QNlog(N))) が間に合わない→ 「候補」ではなく使う辺を確定できないか小課題 4M ≦ 1000
注目の辺

注目の辺よりコスト低

クエリ

注目の辺より安い辺は赤線上のもの
で全てなので、注目の辺が使われる ⇔赤線上の辺でa,b が非連結

小課題 4M ≦ 1000
注目の辺

注目の辺よりコスト低クエリ

a,b が連結にならないように限界まで赤線を伸ばしたときの半分のところが、注目の辺が使われるかどうかの境界小課題 4M ≦ 1000
前処理 : O(M^2α(N))
クエリ処理 : O(QN) or O(M + Qlog(N))

小課題 6 ( 満点 )追加制約なし前処理 : O(M^2α(N)) → 実は O(MNα(N))
クエリ処理 : O(QN) or O(M + Qlog(N))

小課題 6 ( 満点 ) 別解
注目の辺

注目の辺が頂点 a,b を繋いでいるとして、どこまで右に行ったら a と b が連結になってしまうか小課題 6 ( 満点 ) 別解
注目の辺

0 12345678910注目の辺が頂点 a,b を繋いでいるとして、どこまで右に行ったら a と b が連結になってしまうか小課題 6 ( 満点 ) 別解
注目の辺

右から辺を追加 ( 重み : 書かれている番号 )0 12345678910

注目の辺が頂点 a,b を繋いでいるとして、どこまで右に行ったら a と b が連結になってしまうか小課題 6 ( 満点 ) 別解
注目の辺から赤線が伸ばせる限界 : 今までに辺注目の辺 が追加されたグラフで、番号が大きい辺を順にどれだけ取り除いても a,b 間が連結か→ a,b 間のパスに含まれる重みの最大値として考えられる最小値が求まればよい
右から辺を追加 ( 重み : 書かれている番号 )0 12345678910注目の辺が頂点 a,b を繋いでいるとして、どこまで右に行ったら a と b が連結になってしまうか小課題 6 ( 満点 ) 別解
4365ab86
7a,b 間のパスに含まれる重みの最大値として考えられる最小値 :
グラフの最小全域木上での a,b の最短パス (1 つだけ ) が最適であることが証明できる ([1])→ 辺の追加ごとに最小全域木を保持できればよい小課題 6 ( 満点 ) 別解
辺を追加して最小全域木を保持する

4

繋ぐ頂点が非連結のとき→ 繋ぐだけ35ab26

小課題 6 ( 満点 ) 別解
辺を追加して最小全域木を保持する

43a52b6

繋ぐ頂点が連結のとき :辺は右から追加しているので追加する辺の重みは他のどの辺の重みよりも小さい→ ループの中で重み最大のものを消す

小課題 6 ( 満点 ) 別解
辺を追加して最小全域木を保持する

43a2b6繋ぐ頂点が連結のとき :辺は右から追加しているので追加する辺の重みは他のどの辺の重みよりも小さい→ ループの中で重み最大のものを消す

小課題 6 ( 満点 ) 別解
重み付き森に対して●指定した 2 頂点のパス上で重みが最大の辺の特定●
辺追加 ( 閉路はできない )●辺削除
この問題では各 O(N) で良いので簡単 → 合計 O(MN + Q)

小課題 6 ( 満点 ) 別解
重み付き森に対して●指定した 2 頂点のパス上で重みが最大の辺の特定●
辺追加 ( 閉路はできない )●辺削除
この問題では各 O(N) で良いので簡単 → 合計 O(MN + Q)
もっと減らせる
Link-Cut Tree 等で各 O(log(N)) → 合計 O(N + Mlog(N) + Q)

参考文献[1] "Widest path problem", Wikipedia
https://en.wikipedia.org/wiki/Widest_path_problem