2015年5月3日日曜日

Hacker Rank : Even Tree

問題

https://www.hackerrank.com/challenges/even-tree
木が与えられるので、エッジを取り除いてノード数が偶数であるような木幾つかに分解したいので最も多くエッジを取り除くためにはどうすれば良いかを求める問題。

解法

各エッジに対して「このエッジを取り除いて二つに木を分割した時に双方の木に含まれるノード数がどちらも偶数である」ならば、そのエッジを取り除く。そうでなければ取り除かない
とすれば良い。ノード数が800なので十分間に合う。

0 件のコメント:

コメントを投稿