hotpepsiの練習帳

SRM 658

15:13

https://competitiveprogramming.info/topcoder/srm/round/16461/div/1

Div1 Easy (300) OddEvenTree

問題

• N個の頂点からなる木がある
• それぞれの頂点の距離の偶奇が与えられる
• 構成が可能なら辺を求める

方針

• まず必要条件について考える
• 同じ頂点同士は距離ゼロなので偶数
• 隣り合う頂点は奇数なので、一つ以上奇数が存在すること
• 頂点が3以上のときは、一つ以上偶数が存在すること
• 頂点a-b-cについて、経路a-bの偶奇と、経路b-c+c-aの偶奇が一致すること
• 必要条件を満たしたら、奇数同士の頂点aとbを辺で結び、残りの頂点をaとbの偶奇からどちらかに追加していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_658/OddEvenTree.cpp

結果

o-- 146.27pt 271st/497 rating 1313 -> 1350 (+37)

これが正しいとすると、奇数を一つ見つけてから貪欲につなげて、そのあと矛盾があるかどうか判定したほうが楽そう。

http://togetter.com/li/817290