🌳

[ABC062 A] Grouping

2024/02/29に公開

Ruby

同じグループに属するか調べる問題。

シンプルな解き方

グループの構図が、

G = [
  [1, 3, 5, 7, 8, 10, 12],
  [4, 6, 9, 11],
  [2],
]

となっている。

そこで、たとえば 1 と 3 であれば、それぞれのインデックスを求める。

G.find_index { |e| e.include?(1) }  # => 0
G.find_index { |e| e.include?(3) }  # => 0

すると、両方 0 なので同じグループだとわかる。

同様に 4 と 2 なら、

G.find_index { |e| e.include?(4) }  # => 1
G.find_index { |e| e.include?(2) }  # => 2

異なるグループだとわかる。

実行時間が気になる場合は Set 型にしておくと 121 ms から 46 ms まで短縮できる。

富豪的な解き方

同じグループの要素を1つずらしのペアにして、

edges = G.flat_map { |e| e.each_cons(2).to_a }  # => [[1, 3], [3, 5], [5, 7], [7, 8], [8, 10], [10, 12], [4, 6], [6, 9], [9, 11]]

素集合森を作り、

ds = DisjointSet[edges]  # => 親:{1=>3, 3=>3, 5=>3, 7=>3, 8=>3, 10=>3, 12=>3, 4=>6, 6=>6, 9=>6, 11=>6} 構図:{3=>[1, 3, 5, 7, 8, 10, 12], 6=>[4, 6, 9, 11]} 節数:{3=>7, 6=>4} 木数:2 高さ:{3=>2, 6=>2}

同じグループかを確認する。

ds.same?(1, 3)  # => true
ds.same?(4, 2)  # => false

このように A 問題であっても素集合データ構造を無駄に活用していきたい。

コード (AC)

シンプルな解き方

X, Y = gets.split.collect(&:to_i)       # => [2, 4]
G = [[1, 3, 5, 7, 8, 10, 12], [4, 6, 9, 11], [2]].collect(&:to_set)
x = G.find_index { |e| e.include?(X) }  # => 2
y = G.find_index { |e| e.include?(Y) }  # => 1
ans = x == y                            # => false
puts ans ? "Yes" : "No"

富豪的な解き方

X, Y = gets.split.collect(&:to_i)               # => [2, 4]
G = [[1, 3, 5, 7, 8, 10, 12], [4, 6, 9, 11], [2]]
edges = G.flat_map { |e| e.each_cons(2).to_a }  # => [[1, 3], [3, 5], [5, 7], [7, 8], [8, 10], [10, 12], [4, 6], [6, 9], [9, 11]]
ans = DisjointSet[edges].same?(X, Y)            # => false
puts ans ? "Yes" : "No"

シンプルな解き方

富豪的な解き方

コード (AC)

Discussion