🌳
[ARC111 B] Reversible Cards
普通の木か見分ける問題。
問題を理解する
ひとことで言えば、
- カード毎に裏表を適当に選んだときの最大色数は？
になる。たとえば次の2枚のカードがあったとき、
| 表 | 裏 |
|---|---|
| 白 | 黒 |
| 白 | 黒 |
「白 → 白」よりも「白 → 黒」を選択したときのほうが色数が増える。したがって答えは 2 (色) になる。
他のパターンで考える
4枚のカードを順に見ていく。
| 表 | 裏 | 考え方 | 色数 |
|---|---|---|---|
| 白 | 黒 | とりあえず片方を選択してみる | +1 |
| 白 | 黒 | 1枚目と同じカードなので反対の色を選択する | +1 |
| 白 | 黒 | また同じ。どっちを選択しても色数が増えないので飛ばす | |
| 赤 | 青 | どっちも初登場なので、どちらかを選択して1色増える | +1 |
答え → 3
グラフ化する
上のパターンを元に裏表を辺にしたグラフをイメージする。その際に辺の矢印が選択した方を指すようにする。
選択した方を矢印で指すようにしたのであたりまえだが、こうしてできたグラフは「矢印の数 = 色数」になっている。
そして「白黒」の連結成分に着目すると、同じ「白黒」だけを使ったカードをこれ以上追加しようとしても矢印が増やせない。したがって、辺が多すぎる木の色数は「節の数」になる。
一方「赤青」の連結成分は無駄のない普通の木である。ここで仮に辺を減らせないか考えてみるが、辺を無くすとこの木自体がなくなってしまう。したがって、普通の木の色数は「節の数 - 1」になる。
| 種類 | 色数 |
|---|---|
| 辺が多すぎる木 | 節の数 |
| 普通の木 | 節の数 - 1 |
ここまでくれば、どちらの木かを見分けるだけの問題だと気づく。
見分け方
↓ グラフと
↓ 素集合森を
比べる。
グラフでの辺が 1 つの「赤青」は素集合森でも 1 つなので「普通の木」だとわかる。一方、辺が 3 つの「白黒」は素集合森では 1 つなので「辺が多すぎる木」だとわかる。
| 連結成分 | 種類 |
|---|---|
| 白黒 | 辺が多すぎる木 |
| 赤青 | 普通の木 |
考え方の最適化
「連結成分の種類」を調べてから「節の数」または「節の数 - 1」を色数とする二段階の考え方は、単に「グラフとしてみたときの辺の数」と「素集合森での節の数」の小さい方を色数とする考えに置き換えることができる。
これは「グラフとしてみたときの辺の数」が多すぎたときだけ「素集合森での節の数」で制限するイメージになる。
コード (AC)
N = gets.to_i # => 12
XY = N.times.collect { gets.split.collect(&:to_i) } # => [[5, 2], [5, 6], [1, 2], [9, 7], [2, 7], [5, 5], [4, 2], [6, 7], [2, 2], [7, 8], [9, 7], [1, 8]]
ds = DisjointSet[XY]
p ds.groups.keys.sum { |e| [ds.edge(e), ds.size(e)].min } # => 8
Discussion