[ABC333 D] Erase Leaves
最大の木の大きさを求める問題。
一本の木
問題文で与えられるグラフは「木」と書いてある。これは節がすべて繋っているということであり、塊になっているということなので、削除前の木の形については考える必要がない。
削除を言い換える
「X を削除する」を「X を使わずに作る」に言い換える。なぜなら素集合データ構造は削除ができないから。
どこから手をつけるか
なんとなく削除したい節に繋がっている「短かい方」から削るのが効率的に思える。しかし、節が多いとその「短かい方」の判断が難しかったりする。そこで、削っていくのはいったん置いといて、削除する節を使わず木を作るだけにしてみる。
いろんなパターンで試す
架空の一本の木から節 A を削除 (A を使わずに作成) したあとの状態が次のようになっていたとき、これはひと目、(Aを削除する) 最小コストは 1 だろう。B または C に繋っていた A が外れただけだと推察できる。
別の架空の一本の木から D を削除したあとが次のようになったとき、これは D にくっついていた E が外れたのち D が削除できたと思われるので (Dを削除する) 最小コストは 2 だろう。
別の架空の一本の木から D を削除したあとが次のようになったとき、これはひと目ではわからないが、なんとなく D にくっついていた A-B-C と I が外れたことで D が削除できたように見えるので、(Dを削除する) 最小コストは 5 だろう。
問題の入力例1で 1 を削除すると次のようになる。これは二つの木のどちらから落としていったとしても 1 を外せるので、どちらから落としたのか判然としないものの、最小コストだけ言えば 5 だろう。
削除後に同じ大きさの木が2つできてしまうこの例は、わかりやすくヒントを伝える目的であればあまり良い例ではなかったように感じる (小声)
続いて、入力例2で 1 を削除すると次のようになる。これは最初の架空の木と同じで、ひと目、最小コスト 1 だろう。
入力例3で 1 を削除すると次のようになる。これは難しいが、これまでの要領でいけば、24 と 16 と 1 の木の大きさの合計=12が最小コストだろうか。
なんとなくをはっきりさせる
このようにして、すべてのパターンでなんとなく最小コストが見えたわけだけど、この理屈を客観的に言語化すると、「コストを低くするには、最大の木だけが生き残っていると考えた方が都合がいいから、その最大の木を除いた節の数を数えた」と言える。
最大の木を除いた節の数を求める簡単な方法
もちろん言葉通りに最大の木を除いた節の数をカウントしてもいいが、計算時間の面から言えば「全体の節の数」から「最大の木の大きさ」を引くだけでそれは求まる。
コード (AC)
N = gets.to_i # => 9
UV = N.pred.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 4], [2, 5], [1, 6], [6, 7], [7, 8], [7, 9]]
xy = UV.reject { |e| e.include?(1) } # => [[2, 3], [2, 4], [2, 5], [6, 7], [7, 8], [7, 9]]
ds = DisjointSet.new(1..N).unites(xy)
p ds.nodes.count - ds.tree_size_max # => 5
Discussion