オンサイトで未確認

ukuku09の活動記録。

ARC093 E - Bichrome Spanning Tree

これ好き。

RUPC2018へ向かう新幹線の中で、うしさん(@ei1333)に確認しながら考えた。

問題

E - Bichrome Spanning Tree

解法

「辺iを含む全域木のうち、最小の重みがX未満」を満たす辺iの本数と、「辺jを含む全域木のうち、最小の重みがX」を満たす辺jの本数を数えると、あとは適切な計算をすればこの問題に対する答えが求まる。

上記の辺の本数は、最小全域木アルゴリズムであるKruskal法を利用することで{\it O}(M^2)程度で求められる。

グラフの最小全域木の重み>Xの場合

どのように辺を塗っても問題の条件を満たすことができないので、答えは0である。

グラフの最小全域木の重み=Xの場合

ある最小全域木に含まれる辺のうち、1本でも色が異なれば、問題の条件を満たすことに気づく。(最小全域木は複数存在しうる)

よって、いずれかの最小全域木に含まれる辺の本数mがわかれば

_mC_1+_mC_2+...+_mC_{m-1}=2^m-2

m本の辺の可能な塗り方の総数を求めることができる。

残りのM-m本の辺は当然自由に彩色できる。すなわちその塗り方の総数は、m'=M-mとすれば

_{m'}C_0+_{m'}C_1+...+_{m'}C_{m'}=2^{m'}

と書ける。

これを先の値とを掛け合わせて答えを得る。

グラフの最小全域木の重み<Xの場合

「辺iを含む全域木のうち、最小の重みがX未満」を満たす辺iの集合を\bf Aとすると、\bf Aに含まれる辺はすべて同じ色で塗らなければならない。

なぜなら1本でも色が異なれば、\bf Aの定義より、その辺を含む全域木の最小の重みはX未満で、それは白と黒の辺を両方含むことになり、問題の条件を満たさないためである。

よって、\bf Aの塗り方はすべて白に塗るかすべて黒に塗るかの2通りに限られる。

次に「辺jを含む全域木のうち、最小の重みがX」を満たす辺jの集合を\bf Bとする。ここで、\bf Bに含まれる辺を含む全域木のうち、重みが最小の全域木は、必ず\bf Aに含まれる辺を含んでいる。

これは最小全域木に辺を1本追加すると、その辺を含む閉路がちょうど一つできて、そのうちの1本を取り除くことで再び全域木を得られることから導ける。

これより、\bf Bの塗り方は、1本以上の辺を\bf Aの辺と異なる色にする総数なので、m=|{\bf B}|として

_mC_1+_mC_2+...+_mC_m=2^m-1=2^{|{\bf B}|}-1

となる。

残りのM-|{\bf A}|-|{\bf B}|本の辺は自由に彩色できるので、その塗り方の総数は2^{M-|{\bf A}|-|{\bf B}|}通りである。

したがって、求めるべき答えは2*(2^{|{\bf B}|}-1)*2^{M-|{\bf A}|-|{\bf B}|}である。

ソースコード

ARC093 E - Bichrome Spanning Tree

感想

modを取り忘れない💢💢💢