🌳

[ABC229 E] Graph Destruction

2024/02/20に公開

Ruby

削除するために最初から作るのだが頂点に対応する辺の選択が難しい問題。

考察

辺を削除するために最初から作っていくような問題はあるが、この問題は辺ではなく「頂点」になっているため難易度が高い。

解き方

木の数を求める
逆から頂点を追加する
その頂点に連結する辺を接続する

以上を繰り替えして (1) で求めた木の数の並びを反転する。

シミュレーション

2つの辺 B-C B-D が繋がっているグラフ A C-B-D で A→D の順で落としていく例で考えると、

実行	グラフ	木	備考
	A C-B-D
-A	C-B-D	1
-B	C D	2	B-C B-D の辺が一気に外れる
-C	D	1
-D		0

となり 1 2 1 0 が答えになる。しかし、グラフは削除できないため D→A の順で作り、

実行	グラフ	木	備考
		0
+D	D	1
+C	C D	2
+B	C-B-D	1	B-C B-D の辺を同時に作る
+A	A C-B-D

木の数 0 1 2 1 を反転した 1 2 1 0 が答えになる。

頂点に影響する辺

辺は B-C B-D なので順に落としていくなら普通に、

実行	影響する辺
-A
-B	C D
-C	B
-D	B

となり、逆から作る場合は次のように、

実行	影響する辺
+D	B
+C	B
+B	C D
+A

単に反転させればよさそうだが、

消していく世界線だと B はすでに消されているから、D は B のことを知っていてはいけない
消していく世界線だと B を消す前に D は存在するから、B は D のことを知っていてもよい

つまり、

自分より若い頂点はすでに消されているので知っていてはいけない
自分より古い頂点はすでに存在するので知っている

となるため、

実行	影響する辺
+D
+C
+B	C D
+A

が、正しい。

コードで言えば、辺 (a, b) は (a < b) の関係で並んでいるので、

edges = Hash.new { |h, k| h[k] = [] }
AB.each do |a, b|
  edges[a] << [a, b]
  edges[b] << [a, b]
end
edges  # => {"B"=>[["B", "C"], ["B", "D"]], "C"=>[["B", "C"]], "D"=>[["B", "D"]]}

ではなく、

edges = Hash.new { |h, k| h[k] = [] }
AB.each do |a, b|
  edges[a] << [a, b]
end
edges  # => {"B"=>[["B", "C"], ["B", "D"]]}

としないといけない。

シミュレーションに合わせた実装

AB = [["B", "C"], ["B", "D"]]
edges = Hash.new { |h, k| h[k] = [] }
AB.each { |a, b| edges[a] << [a, b] }
ans = []
ds = DisjointSet.new
("A".."D").reverse_each do |node|
  ans << ds.tree_count
  ds.make_set(node)
  ds.unites(edges[node])
end
ans.reverse  # => [1, 2, 1, 0]

提出したコード (AC)

N, M = gets.split.collect(&:to_i)                    # => [6, 7]
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 4], [1, 5], [2, 4], [2, 3], [3, 5], [3, 6]]

edges = Hash.new { |h, k| h[k] = [] }
AB.each { |a, b| edges[a] << [a, b] }
edges                                                # => {1=>[[1, 2], [1, 4], [1, 5]], 2=>[[2, 4], [2, 3]], 3=>[[3, 5], [3, 6]]}

ans = []
ds = DisjointSet.new
N.downto(1) do |i|
  ans << ds.tree_count
  ds.make_set(i)
  ds.unites(edges[i])
end
ans.reverse                                          # => [1, 2, 3, 2, 1, 0]

試行錯誤の記録

毎回素集合森を作るのは遅すぎる

TLE

N, M = gets.split.collect(&:to_i)                    # => [6, 7]
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 4], [1, 5], [2, 4], [2, 3], [3, 5], [3, 6]]
(1..N).each do |i|
  need = [*1..i]
  edges = AB.reject { |a, b| need.include?(a) || need.include?(b) }
  nodes = [*1..N] - need
  ds = DisjointSet.new(nodes).unites(edges)
  p ds.tree_count                                    # => 1, 2, 3, 2, 1, 0
end

1..N の順でその頂点を使わずに「毎回素集合森を作る」方法では TLE になる。根本的に方針が間違っている。N..1 の順で「素集合森を作るのは1度だけ」としないといけない。

頂点に絡む辺を探す処理が遅すぎる

TLE

N, M = gets.split.collect(&:to_i)                    # => [6, 7]
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 4], [1, 5], [2, 4], [2, 3], [3, 5], [3, 6]]
ans = []
ds = DisjointSet.new
N.downto(1) do |i|
  ans << ds.tree_count
  need = (i..N).to_set
  edges = AB.find_all { |a, b| need.include?(a) && need.include?(b) }
  ds.make_set(i)
  ds.unites(edges)
end
ans = ans.reverse                                    # => [1, 2, 3, 2, 1, 0]
puts ans

方針は合っているものの頂点に繋がる辺を探す処理に時間がかかりすぎている。これは事前にテーブルを用意して頂点に対応する辺を O(1) で取れるようにしないといけない。

類題

参考

https://atcoder.jp/contests/abc229/editorial/2958