🌳
[ABC279 F] BOX
根と箱の相互変換が重要な問題。
考察
- 箱を配列の配列(もしくは Set 型の配列)にしていては間に合わない
- ボールは混ざる一方なので素集合森と相性が良い
- 混ざっている情報は素集合森が持っているのだから箱には「根」を入れておくだけでよい
- クエリ3のために「ボール→根→箱」の情報を記録する
解き方
- 別の箱に移したとき移動先のボールと移動元のボールを併合する
- 箱には、その箱に入っているボールの代表を入れておく
- 代表でなくても同じ根を持った節ならどれでもよい
- なので最後に入れたボールと決めてもよい
- が、代表と決めておくと、なんとなくわかりやすい
- 併合のタイミングで「根」から「箱」の対応を記録する
- クエリ3で「ボール→根→箱」を調べるのに使う
- ここでは必ず「根」をキーにしなといけない
- 箱には根が入っているのだから箱を順に探せば記録する必要はない
- ただそれでは線形探索になってしまう
例1のシミュレーション
| コマンド | 引数 | 箱 | 素集合森 | 根→箱 | 表示 |
|---|---|---|---|---|---|
| 確認 | 5 | 1 2 3 4 5 | 5 | ||
| 移動 | 1 ← 4 | 4 2 3 _ 5 | 1-4 | 4→1 | |
| 生成 | 1 | 4 2 3 _ 5 | 1-4-6 | 4→1 | |
| 生成 | 4 | 4 2 3 7 5 | 1-4-6 | 4→1 7→4 | |
| 確認 | 7 | 4 2 3 7 5 | 1-4-6 | 4 | |
| 移動 | 3 ← 1 | _ 2 4 7 5 | 1-4-6-3 | 4→3 7→4 | |
| 確認 | 4 | _ 2 4 7 5 | 1-4-6-3 | 3 | |
| 移動 | 1 ← 4 | 7 2 4 _ 5 | 1-4-6-3 | 4→3 7→1 | |
| 確認 | 7 | 7 2 4 _ 5 | 1-4-6-3 | 1 | |
| 確認 | 6 | 7 2 4 _ 5 | 1-4-6-3 | 3 |
- 素集合森で辺を持たない節は省略している
- 「根→箱」に登録がないものは初期値のままなのでボールと根と箱は同じ
- 素集合森の根(代表値)は実装によって変わる
コード (AC)
1353 ms
N, Q = gets.split.collect(&:to_i) # => [5, 10]
OP = Q.times.collect { gets.split.collect(&:to_i) } # => [[3, 5], [1, 1, 4], [2, 1], [2, 4], [3, 7], [1, 3, 1], [3, 4], [1, 1, 4], [3, 7], [3, 6]]
box = N.next.times.to_a # => [0, 1, 2, 3, 4, 5]
root = {} # => {}
k = N # => 5
ds = DisjointSet.new
OP.each do |command, x, y|
case command
when 1
a, b = box[x], box[y]
if a || b
a ||= b # どちらかが空の場合を
b ||= a # 考慮して埋めておく
ds.unite(a, b)
r = ds.root(a)
root[r] = x # クエリ3の「根→箱」変換用
box[x] = r # 追加先の箱には代表を入れておく
box[y] = nil # 移動元の箱は空になる
end
when 2
k += 1 # 新しいボール
ds.unite(box[x] || k, k) # 追加先が空の場合を考慮しつつ併合
r = ds.root(k)
root[r] = x # クエリ3の「根→箱」変換用
box[x] = r # 追加先の箱には代表を入れておく
when 3
p root[ds.root(x)] || x # => 5, 4, 3, 1, 3
end
end
Discussion