hotpepsiの練習帳

SRM 666

01:12

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

Div1 Easy (222)

問題

• N個の頂点からなる木が与えられる
• 1ステップで辺を一つ移動できる
• ノード0からLステップで訪問できる異なる頂点の最大数を求める

方針

• (終了後)
• 一番遠い葉までの距離Dを求める
• 近いノードは往復してノード0に戻り、そのあと一番遠いノードに移動すればいい
• 残りのノード数は(N-D-1)個
• 近いところは(L-(N-D-1))÷2個訪問できる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_666/WalkOverATree.cpp

結果

--- 0pt 186th/343 rating 1400 -> 1358 (-42)

全く思いつかなかった。良い問題。

http://togetter.com/li/865547