Facebook HC Round 2

NHC

なんか問題が良すぎる...。

A

N点のグラフが与えられるので、最初のK点を含む閉路がなくなるように枝を削るときの最小数を答えよ、という問題。


まず、K点内で閉路があっては論外なので、削る。UnionFind使って、同じグループ内だったら削る。ついでにそれ以外のやつらもUnionFindでグループをまとめておく。後はK点からその他の辺へ既存の枝がなければ追加して良くて、それ以外は削る。最後に削った数を答えるだけ。


全部UnionFindでできる気がしてきた...。

B

グループのマージ順序が与えられるので、それにしたがって階層木を作る。ただし、木の次数がKを越えてはいけない。そのときの木の深さで一番小さいものを答えよ、という問題。


愚直にやるだけ。マージするときに、深さと可能な最小次数のペアを覚えておいて、次にマージするときに上にいくか下にいくかを検討する。

C

長さNの配列から長さRの配列を作る。二点をランダムに選らんで、その間にある要素がK種類以上である確率を求めよ、という問題。


Kが1の場合はちょっとめんどくさいので、必ずうまくいくとして例外処理しておく。


後は、左側の点が決まったら、右側の点はどこ以降にあるかを考える。右側の点を固定すると、何種類の要素があるかは比較的簡単に(面倒ではあるものの)計算でき、これは広義単調に増加する。なのでバイナリサーチできる。後は、左側の点がNずれると、右側の点もNずれる(ような配列の拡張をしている)ので、N通りだけ調べてやれば、ループするから、簡単に加算できる。左右の選択順序が二通りあるので(K=1の場合を除去してあるから、同じ点を選択することは考慮しなくて良い)合計するときに倍してあげれば、全部で何通りか分かる。全体の選び方は範囲の長さの二乗。後は約分すれば良さそう。


実はしゃくとり法を使えば簡単だそうで...。