[ABC350 D] New Friends
完全グラフの特徴を学ぶ問題。
前提知識
完全グラフの辺の数を求める式 n * (n - 1) / 2 はどこから来たのか？
まず、
- n 個から r 個選ぶのは nCr
- nCr は nPr / r! のこと
- r! は r から 2 までカウントダウンしながら掛け算
- nPr は n から r 回カウントダウンしながら掛け算
したがって、たとえば 4 個から 2 個選ぶには 4P2 / 2! で、
4 * 3 / 2 # => 6
になる。
それはいったん置いといて、nCr を使ってグラフ上の辺を作るため2つの頂点を選ぶとすれば、r は 2 固定になる。そうすると nPr は本来 (n - 0) * (n - 1) * (n - 2) * (n - 3) …… と続くけど r = 2 なら、(n - 0) * (n - 1) までの固定になる。そこに仮で頂点数を n = 4 としてみると、
n = 4
(n - 0) * (n - 1) / 2 # => 6
(4 - 0) * (4 - 1) / 2 # => 6
4 * 3 / 2 # => 6
となって最初の式と一致する。だから完全グラフの辺の数は n * (n - 1) / 2 で求まる。
参照
- https://www.try-it.jp/chapters-4751/sections-4752/lessons-4845/
- https://www.try-it.jp/chapters-4751/sections-4752/lessons-4805/
問題を要約する
- A-B-C の関係の A-C を友達にしたい
- 全体で何件可能か？
考え方
- 完全グラフの辺の数 - 現状の辺の数 = 友達にできる数
これをすべての連結成分に対して行う。その連結成分を知るために素集合森を作る。
3頂点でのシミュレーション
頂点 A B C を用意して、
可能な限り辺を貼った状態が、
完全グラフの 3 本になる。
その 3 本は、頂点数 n = 3 から n * (n - 1) / 2 で求まる。
3 * (3 - 1) / 2 # => 3
一方、現状が、
2 本だったすれば、
- 理想は3本 - 今は2本 → 残り1本
で、あと1ヶ所友達にできる。
この例は、頂点数 3 に対して完全グラフの辺の数も 3 になってわかりづらい。
例1のシミュレーション
頂点 1 2 3 4 を用意して、
可能な限り辺を貼った状態が、
完全グラフの 6 本になる。
その 6 本は、頂点数 n = 4 から n * (n - 1) / 2 で求まる。
n = 4
n * (n - 1) / 2 # => 6
一方、現状は、
3 本なので、
- 理想は6本 - 今は3本 → 残り3本
で、あと3ヶ所友達にできる。
解説の模範解答風 (AC)
N, M = gets.split.collect(&:to_i) # => [5, 3]
AB = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [1, 4]]
ds = DisjointSet.new(1..N).unites(AB) # => 親:{1=>2, 2=>2, 3=>2, 4=>2, 5=>5} 構図:{2=>[1, 2, 3, 4], 5=>[5]} 節数:{2=>4} 木数:2 高さ:{2=>2}
sum = ds.groups.sum { |_, g| g.size * (g.size - 1) / 2 } # => 6
p sum - M # => 3
現状の辺の数は各「森の大きさ - 1」なので、
ds.groups.sum { |_, g| g.size - 1 } # => 3
でもいいが、遡れば M のことなので最後に引くのは M でいい。
M # => 3
なお、sum を求める部分は、
sum = (1..N).sum { |e| ds.size(e) - 1 } / 2 # => 6
として「頂点ごとに所属する木の大きさ - 1」の合計の半分でも求まるようだが、どういう考え方なのかはよくわからない。
Discussion