hotpepsiの練習帳

SRM 630

14:49

Div1 Easy (250) Egalitarianism3

問題

• N個の都市がある
• それぞれの都市はN-1本の道路で接続されておりそれぞれの長さが与えられる
• どの2都市の距離も全て等しいという条件を満たす最大の都市数を求める

方針

• とりあえずWFで距離を求める
• 終了
• 2点を決めてsetに突っ込んでおく
• 今までに存在する点すべてと距離が同じものを足す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_630/Egalitarianism3.cpp

結果

xxx -1 -25pts 441st/465 rating 1613 -> 1453 (-160)

N<=2のときNになるという考察が足りなかった。

解がスター状になるといえばSRM 566のPenguinSleddingも。

http://togetter.com/li/709546