🌳
[ABC214 D] Sum of Maximum Weights
木の大きさを掛け合わせていく問題。
解法
問題が理解できないため解法から書くと、
- 最初に重さで並び換える (なぜ？)
- 「接続する互いの木の大きさ * 重さ」を繰り返して累積和を求める
となる。
例1のシミュレーション
初期状態
3つの木がある。
1ターン目
1 と 2 を接続するときの重みが 10 なので
- 1の木(1) * 2の木(1) * 重み(10) = 1 * 1 * 10 = 10
2ターン目
2 と 3 を接続するときの重みが 20 なので
- 2の木(2) * 3の木(1) * 重み(20) = 2 * 1 * 20 = 40
答え
得られた 10 と 40 を足して 50
どゆこと？
この問題は何がしたいのだろうか？ 何か現実世界で解決したい問題に置き換えたいのだけどよくわからない。その原因は、そもそも重みで並び換える理由がわかってないからかもしれない。例1はもとから並び換えられているので、あえて逆にして計算してみる。
あえて逆
重み正順
1 * 1 * 10 # => 10
2 * 1 * 20 # => 40
10 + 40 # => 50
あえて逆
1 * 1 * 20 # => 20
1 * 2 * 10 # => 20
20 + 20 # => 40
すると、少し減ってしまった。これはもしかしたら「膨らませたあとで大きな値を掛けた方がより膨らむから大きな値をあとに持ってきている」ということか？ Slay the Spire で言うところの触媒(2倍)と触媒+(3倍)があったときに毒を最大限に溜めてから最後の最後で3倍化した方が効果的だから触媒+をとっておくみたいな──そう考えるとわかったような気がする。
例2の簡易シミュレーション
1 * 1 * 1 # => 1
2 * 1 * 2 # => 4
1 * 3 * 5 # => 15
4 * 1 * 14 # => 56
1 + 4 + 15 + 56 # => 76
コード (AC)
N = gets.to_i # => 3
UVW = N.pred.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 10], [2, 3, 20]]
ds = DisjointSet.new
acc = 0
UVW.sort_by { |_, _, w| w }.each do |x, y, w|
v = ds.size(x) * ds.size(y) * w # => 10, 40
acc += v
ds.unite(x, y)
end
p acc # => 50
Discussion