🌳
[ABC183 F] Confluence
併合時に他の情報もマージする問題。
ヒントになる言葉や言い回し
- 合流
→ 素集合データ構造 - 一度合流した生徒が分かれることはありません
→ グループを分割することができない素集合データ構造を暗示、いや明示している
本人だけが知っている情報
例1の入力例では、生徒たちが順にクラス 1 2 3 2 1 に属していると最初に伝えられる。
ここで生徒1の立場で本人の知っている情報を、
- 本人がクラス1に属している
- そのクラスの人数は1人(本人自身)
とする。
同様にして各自の立場で知っている情報をまとめると次のようになる。
| 生徒 | 情報 |
|---|---|
| 1 | クラス1(1人) |
| 2 | クラス2(1人) |
| 3 | クラス3(1人) |
| 4 | クラス2(1人) |
| 5 | クラス1(1人) |
そして、この情報を合流するたび、合流先にマージしていく。
ここからは想像力を働かせ、特定の生徒に憑依して考えるのが重要である。
シミュレーション
1ターン目
1 と 2 が合流する。問題にはどちらがどちらに合流するかは書かれていない。合流する向きについての考え方がそもそもない。しかし、合流の向きが重要になる。合流の向きは木の併合処理に合わせればよい。
木の併合結果を見ると 1 が 2 に合流したので 1 の知っている情報を 2 に移す。
| 生徒 | 情報 |
|---|---|
| 1 | |
| 2 | クラス1(1人), クラス2(1人) |
| 3 | クラス3(1人) |
| 4 | クラス2(1人) |
| 5 | クラス1(1人) |
2ターン目
5 が 2 に合流したのがわかったので 5 の情報を 2 に移す (足す)。
| 生徒 | 情報 |
|---|---|
| 1 | |
| 2 | クラス1(2人), クラス2(1人) |
| 3 | クラス3(1人) |
| 4 | クラス2(1人) |
| 5 |
3ターン目
生徒1と合流しているグループでクラス1に属している人数は？
生徒1が合流しているグループの情報を握っているのは生徒2なので、その情報からクラス1の人数を拾う。
| 生徒 | 情報 |
|---|---|
| 1 | |
| 2 | クラス1(2人), クラス2(1人) |
| 3 | クラス3(1人) |
| 4 | クラス2(1人) |
| 5 |
結果: 2 人
4ターン目
3 が 4 に合流したのがわかったので 3 の持っていた情報を 4 に移す。
| 生徒 | 情報 |
|---|---|
| 1 | |
| 2 | クラス1(2人), クラス2(1人) |
| 3 | |
| 4 | クラス2(1人), クラス3(1人) |
| 5 |
5ターン目
生徒3に合流しているグループでクラス4に属している人数は？
生徒3が合流しているグループの情報を握っているのは生徒4なので、その情報からクラス4の人数を拾う。しかし、クラス4に属している人はいなかった。
結果: 0 人
コード (AC)
N, Q = gets.split.collect(&:to_i) # => [5, 5]
C = (1..N).zip(gets.split.collect(&:to_i)).to_h # => {1=>1, 2=>2, 3=>3, 4=>2, 5=>1}
A = Q.times.collect { gets.split.collect(&:to_i) } # => [[1, 1, 2], [1, 2, 5], [2, 1, 1], [1, 3, 4], [2, 3, 4]]
m = Hash.new { |h, k| h[k] = Hash.new(0) } # => {}
(1..N).each { |e| m[e][C[e]] += 1 }
m # => {1=>{1=>1}, 2=>{2=>1}, 3=>{3=>1}, 4=>{2=>1}, 5=>{1=>1}}
ds = DisjointSet.new
A.each do |t, x, y|
if t == 2
p m[ds.root(x)][y] # => 2, 0
else
if ds.different?(x, y) # 合流していないなら
x = ds.root(x)
y = ds.root(y)
ds.unite(x, y) # 合流する
if ds.root(x) == x # x ← y なら
x, y = y, x # x → y に統一して
end
m[y].update(m[x]) { |_, *v| v.sum } # x → y の方向でマージする
end
end
end
Discussion