[ABC120 D] Decayed Bridges
森を作りながら「木の大きさ×木の大きさ」を求める問題。
前提知識
N 個の組み合わせは何通り？
N * (N - 1) / 2 で求まるらしいのだが、どこかで習った記憶がまるでない。
自力で計算してみると、
| N | 計算過程 | X通り |
|---|---|---|
| 5 | 4 + 3 + 2 + 1 | 10 |
| 4 | 3 + 2 + 1 | 6 |
| 3 | 2 + 1 | 3 |
| 2 | 1 | 1 |
| 1 | 0 | 0 |
となるが、巷の公式を使うと、たしかに一回で求まる。
5 * (5 - 1) / 2 # => 10
4 * (4 - 1) / 2 # => 6
3 * (3 - 1) / 2 # => 3
2 * (2 - 1) / 2 # => 1
1 * (1 - 1) / 2 # => 0
X個とY個の組み合わせは何通り？
これは難しく考えてはいけない。9 個と 9 個の組み合わせであれば 9 * 9 = 81 通りである。
ことわざ
- 橋を見たら素集合データ構造と思え
言葉の置き換え
- 橋の崩落 → 辺の削除
- 島 → 木
すべてを反転する
素集合データ構造は削除が苦手なので、
- 橋を削除するごと不便になっていく
を、
- 橋を作成するごと便利になっていく
に置き換える。こんな発想知ってないと出てこない。具体的には辺のリストを逆から参照していく。注意点としてループ内の処理も逆になる。言葉にすると余計ややこしくなりそうだが「削除した後で不便さを調べる」のではなく「作成する前に便利さを調べる」になる。
例1のシミュレーション
1ターン目
最初はすべての橋がないので便利さ 0
2ターン目
1 と 4 を併合して「1の大きさ(1) * 4の大きさ(1) = 1」だけ便利になり、0 + 1 で 1
3ターン目
同様に 2 と 3 を併合して「2の大きさ(1) * 3の大きさ(1) = 1」だけ便利になったので 1 + 1 で 2
4ターン目
続いて 1 と 3 を併合して「1の大きさ(2) * 3の大きさ(2) = 4」だけ便利になったので 2 + 4 で 6。この時点で便利さは最大になっている。
5ターン目
3 と 4 はもう併合しているので便利さに変化なく 6
元の世界線に戻す
ここで「便利さ順」を「不便さ逆順」に変換する。
不便さの最大は 6
N = 4
max = N * (N - 1) / 2 # => 6
なので、便利さの値
a = [0, 1, 2, 6, 6]
を「不便さの最大 - 便利さ」で反転させ、
a = a.collect { |e| max - e } # => [6, 5, 4, 0, 0]
この並びを逆にすれば答えになる。
a.reverse # => [0, 0, 4, 5, 6]
ショートカットな考え方
「不便さの最大」は最初からわかる (N からわかる) ので「不便さの最大」から「便利さ」を少しずつ引いていく方法もある。その方がショートカットできるし、だいたいの人がそうしている。ただ、すべてを逆にして考えているのに、不便さが介入してくるのに違和感がある。「削除」と「不便」はない世界線で考えたい。したがって便利さを求めてから不便さに変換するようにした。
コード (AC)
N, M = gets.split.collect(&:to_i) # => [4, 5]
AB = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [3, 4], [1, 3], [2, 3], [1, 4]]
v = 0 # 便利さ
av = []
ds = DisjointSet.new
AB.reverse.each do |a, b|
av << v
if ds.different?(a, b) # a, b が併合されていなかったら a, b をこのあと併合することで
v += ds.size(a) * ds.size(b) # 便利になる度合(差分)をどんどん足していく
end
ds.unite(a, b)
end
# 「便利さ」を「不便さ」に反転したのち順番も反転する
max = N * (N - 1) / 2 # => 6
av # => [0, 1, 2, 6, 6]
av = av.collect { |e| max - e } # => [6, 5, 4, 0, 0]
av = av.reverse # => [0, 0, 4, 5, 6]
puts av
Discussion