🌳

[競プロ典型90問 012] Red Painting

2024/02/13に公開

Ruby

二次元グリッドと素集合森の組み合わせ問題。

解き方

塗る
1. 今の場所を塗る
  → make_set(今の場所)
2. 隣接(上下左右)も塗られていたら連結する
  → exist?(隣接) なら unite(今の場所, 隣接)
確認
1. 二点が塗られている？
  → exist?(a) かつ exist?(b)
2. そのうえで二点が繋がっている？
  → same?(a, b)

塗ったフラグについて

塗ったフラグはどのように管理すればよいか？いくつかの実装例を拝見すると、塗ったフラグ専用の変数を別に用意しているケースがすべてだった。たしかに、それはそれでわかりやすい。しかし「素集合森の中に節がある」は、それが「塗った」印でもあるので、わざわざ別に変数を用意する必要はないように思える。

ハッシュ化もどきは必要？

二次元座標を一次元化したりしている実装が見られる。たしかに、それによって速くなるかもしれないが、そもそも「素集合森の節が整数でなければならない」という実装上の都合からきた制約が問題なのではないだろうか。

つまり、二次元座標がそのまま格納できれば、わざわざ二次元座標を一次元化したりするハッシュ化もどきの苦労は不要である。

親切設計の Data

Data (が生成するクラスのインスタンス) は値が同じならハッシュ値も同じになる。

V = Data.define(:x, :y)
V[1, 2].hash  # => -3234047863712868726
V[1, 2].hash  # => -3234047863712868726

コード (AC)

H, W = gets.split.collect(&:to_i)                   # => [3, 3]
N = gets.to_i                                       # => 10
Q = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2, 2], [1, 1, 1], [2, 1, 1, 2, 2], [1, 3, 2], [2, 1, 1, 2, 2], [2, 2, 2, 3, 2], [1, 2, 3], [1, 2, 1], [2, 1, 1, 2, 2], [2, 1, 1, 3, 3]]

V = Data.define(:x, :y) do
  def +(v) = self.class.new(x + v.x, y + v.y)
end

DIRS = [V[0, -1], V[0, 1], V[-1, 0], V[1, 0]]

ds = DisjointSet.new
ans = []
Q.each do |command, y0, x0, y1, x1|
  a = V[x0, y0]
  b = V[x1, y1]
  case command
  when 1
    ds.make_set(a)
    DIRS.each do |e|
      v = a + e
      if ds.exist?(v)
        ds.unite(a, v)
      end
    end
  when 2
    ans << (ds.exist?(a) && ds.exist?(b) && ds.same?(a, b))
  end
end

ans                                                 # => [false, false, true, true, false]
puts ans.collect { |e| e ? "Yes" : "No" }