🌳
[ABC065 D][ARC076 B] Built?
クラスカル法に渡す辺を作るまでが難しい問題。
考え方
- 座標 A B C が A < B < C の関係であれば A-B-C の形にすればいい
- わざわざ離れた A-C で繋ぐ必要はない
- 「座標1 < 座標2 < 座標3」の関係にするにはソートする
- そうなれば必要な辺は A-B と 辺 B-C の二つ
- 辺のコストは A-B で言えば A から B の距離になる
- そうして「辺とコスト」の配列を用意する
- 以上を X, Y 成分毎に行う
- 二つの配列を合体してクラスカル法で作った MST のコストが答え
コード (AC)
796 ms
N = gets.to_i # => 6
XY = N.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 3], [3, 1], [5, 4], [5, 5]]
# X 成分に分離する (このときなんでもよいが頂点IDに相当する値を保持しておく)
x = XY.collect.with_index { |(x, _), i| [x, i] }.sort_by(&:first) # => [[1, 0], [2, 1], [2, 2], [3, 3], [5, 4], [5, 5]]
# [辺(左頂点ID, 右頂点ID), コスト(距離相当)] の配列を作る
x = x.each_cons(2).collect { |(a, l), (b, r)| [[l, r], b - a] } # => [[[0, 1], 1], [[1, 2], 0], [[2, 3], 1], [[3, 4], 2], [[4, 5], 0]]
# Y 座標も同様に行う
y = XY.collect.with_index { |(_, y), i| [y, i] }.sort_by(&:first) # => [[1, 3], [2, 0], [3, 1], [3, 2], [4, 4], [5, 5]]
y = y.each_cons(2).collect { |(a, l), (b, r)| [[l, r], b - a] } # => [[[3, 0], 1], [[0, 1], 1], [[1, 2], 0], [[2, 4], 1], [[4, 5], 1]]
# 二つを合体する
edges = x + y # => [[[0, 1], 1], [[1, 2], 0], [[2, 3], 1], [[3, 4], 2], [[4, 5], 0], [[3, 0], 1], [[0, 1], 1], [[1, 2], 0], [[2, 4], 1], [[4, 5], 1]]
# ここからはクラスカル法に合流する
edges = edges.sort_by { |_, cost| cost } # => [[[4, 5], 0], [[1, 2], 0], [[1, 2], 0], [[0, 1], 1], [[4, 5], 1], [[2, 3], 1], [[3, 0], 1], [[0, 1], 1], [[2, 4], 1], [[3, 4], 2]]
total = 0
ds = DisjointSet.new
edges.each do |edge, cost|
if ds.different?(*edge)
total += cost # => 0, 0, 1, 2, 3
ds.unite(*edge)
end
end
p total # => 3
TLE 対策
ソートする際には必ずキーを明示すること。キーを配列の先頭にして普通にソートすると全体で3倍ほど時間がかかり TLE になる。
Discussion