FHC round1 40. Corporate Gifting

その他

問題

N人の社員がおり、1〜Nの番号が付けられている。1はCTOになっている。
i番の社員の上司がj番の社員であるという情報が与えられる。社員1人につき、上司は1人のみ。


今、すべての社員が上司にN種類の贈り物から1つ選んでプレゼントすることを考える。
各社員は同じ種類の贈り物をしてもよいが、「上司と同じ種類の贈り物は贈れない」。
CTOも贈り物を選ぶが、それは寄付され、社員には渡されない。


N種類の贈り物がそれぞれ1〜Nドルとした場合、この会社の社員が贈り物をする際の金額合計の最小値を求める。

1<=N<=2*10^5

考え方

単純に考えると、社員の関係は木構造になっており、
dp[i][j]:=社員iが贈り物jを選んだ場合の社員iの部下を含めた最小金額
として、ルートノード(CTOの寄付先ノード)からの距離が遠いノードからもとめればよい。


しかし、O(N^2)となってしまうため、メモリ的にも計算量的にも現実的ではない。
いくつか例を見てみると、社員数や構成によらず、あまり高価な贈り物をする社員がいないことがわかる。


そこで、贈り物の金額が最大でどの程度になるかを考える。
ある社員がkドルの贈り物を用意するというのは、その社員の直属の部下が1ドル〜k-1ドルまでの贈り物を用意している場合なので、そのような状態は最低何人の社員が必要か？を考える。
C(k):=kドルの贈り物を用意しないといけない最小社員数
とおいて、CTOがkドル使うと考えると、
C(1)は1人、C(2)は2人になる。
C(3)は、C(1)+C(2)+1かというと、4人では最低金額が2ドルになるので、C(1)+C(2)+1よりは多い人数が必要になる。
C(4)もC(1)+C(2)+C(3)+1について同様で、これよりも多くの人数が必要になると考えられる。


C(1)=1
C(2)=C(1)+1=2
C(3)>=C(1)+C(2)+1=4
C(4)>=C(1)+C(2)+C(3)+1=8
...
となり、C(k)>=2^(k-1)と考えられる。
今回は、N=200,000しか人数がいないので、上記の式では、C(19)>=262144と考えれば、19ドルの贈り物を使うために必要な人数に足りないはず。
したがって、贈り物の金額は18ドルまで考慮すればよくなり、計算量的にも間に合う。


実際は、11ドルまで考えればよい模様？http://oeis.org/A007052
O(N)な解法も公式Editorialで紹介されてる。(あとでやる)

その他

https://www.facebook.com/notes/1047761065239794/
Kroon et al., The Optimal Cost Chromatic Partition Problem for Trees and Interval Graphs
http://blog.ilim.me/hackercup-problem-corporate-gifting