🌳

[ARC056 B] 駐車場

2024/02/24に公開

Ruby

削除するために最初から作るのだが頂点に対応する辺の選択が難しい問題。

考え方

「i番目の駐車スペースに車を駐めると、そこを通れなくなる」を「節iに連結する辺を削除する」に言い換える
i を 1 から N の順として以下をシミュレーションする
- i と S との連結を確認する (連結していたら i を出力する)
- i に連結する辺を削除する
  - 辺の一方の節を j とすると必ず i < j の関係になっている
  - i より前はもう削除したので存在しない
逆に辺がない状態から i を N から i の順として以下をシミュレーションする
- i に連結する辺を作る
  - 辺の一方の節を j とすると必ず i < j の関係になっている ※
  - i より前はもう削除したので存在しない ※
  - 簡単に言えば「i 以上の節を持った辺を作る」だが、i より大きいのはもう作ってあるので単に「i = u な辺を作る」でよい (辺の要素の並びは u < v にしておく)
- i と S との連結を確認する (連結していたら i を出力する)

逆にしても※のルールは変わらない。

例1のシミュレーション

まず、辺は 1-2 2-3 1-3 になっていて 1..3 の順で削除していくと、

節	S(2)との連結	節と連結の辺を削除する	素集合森
			1-2-3
1	1-2 → ○	1と連結の辺 1-2 1-3 を削除する	1 2-3
2	2-2 → ○	2と連結の辺 2-3 を削除する	1 2 3
3	3-2 → ×	3と連結の辺がないのでパス	1 2 3

○○×となるので答えは 1 2 になる。次に、これを逆にすると、

節	節以上の辺と接続する	素集合森	S(2)との連結
3	3以上がないのでパス	1 2 3	3-2 → ×
2	2以上は 2-3 があるので接続	1 2-3	2-2 → ○
1	1以上は 1-2 1-3 があるので接続	1-2-3	1-2 → ○

×○○になるので答えは 2 1 だが 1..N の順で解答しなければならないため 1 2 が答えになり、削除していくシミュレーションの結果と同じになったのがわかる。

例2のシミュレーション

まず、辺が多いと確認しずらいので u < v の並びに整えて全体もソートしておくと見やすい。

u	v
1	2
1	4
1	5
2	3
3	4
3	5

そうしておいてから順に節に関係する辺を落としていくと、

節	S(5)との連結	節と連結の辺を削除する	素集合森
			1-2-3-4-5
1	1-5 → ○	1と連結の辺 1-2 1-4 1-5 を削除	1 2-3-4-5
2	2-5 → ○	2と連結の辺 2-3 を削除	1 2 3-4-5
3	3-5 → ○	3と連結の辺 3-4 3-5 を削除	1 2 3 4 5
4	4-5 → ×	4と連結の辺がないのでパス	1 2 3 4 5
5	5-5 → ○	5と連結の辺がないのでパス	1 2 3 4 5

1 2 3 5 が答えになる。次に反転すると、

節	節以上の辺と接続する	素集合森	S(5)との連結
5	5以上がないのでパス	1 2 3 4 5	5-5 → ○
4	4以上がないのでパス	1 2 3 4 5	4-5 → ×
3	3以上の 3-4 3-5 を接続	1 2 3-4-5	3-5 → ○
2	2以上の 2-3 を接続	1 2-3-4-5	2-5 → ○
1	1以上の 1-2 1-4 1-5 を接続	1-2-3-4-5	1-5 → ○

5 3 2 1 となり同様に反転して 1 2 3 5 が答えになる。

コード (AC)

864 ms

N, M, S = gets.split.collect(&:to_i)                 # => [5, 6, 5]
UV = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 5], [3, 5], [3, 2], [4, 1], [1, 2], [4, 3]]

edges = Hash.new { |h, k| h[k] = [] }
UV.collect(&:sort).each { |u, v| edges[u] << [u, v] }

ans = []
ds = DisjointSet.new
(1..N).reverse_each do |i|
  ds.unites(edges[i])
  if ds.same?(i, S)
    ans << i
  end
end
ans = ans.reverse                                    # => [1, 2, 3, 5]
puts ans

辺を配列のまま持っておく方法

627 ms

N, M, S = gets.split.collect(&:to_i)                 # => [5, 6, 5]
UV = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 5], [3, 5], [3, 2], [4, 1], [1, 2], [4, 3]]

edges = UV.collect(&:sort).sort_by { |u, v| -u }     # => [[3, 5], [3, 4], [2, 3], [1, 5], [1, 4], [1, 2]]

ans = []
pos = 0
ds = DisjointSet.new
(1..N).reverse_each do |i|
  while (u, v = edges[pos]) && u >= i # u == i でもよい
    ds.unite(u, v)
    pos += 1
  end
  if ds.same?(i, S)
    ans << i
  end
end
ans = ans.reverse                                    # => [1, 2, 3, 5]
puts ans

これは参考にさせていただいたブログのロジックで、辺の並びを u の降順にして節以上の辺を while で回して作る方法になっている。edges の参照位置を別に管理しないといけないが、辺を節ごとに分離する前処理を省ける。