hotpepsiの練習帳

SRM 640

02:29

Div1 Easy (250) ChristmasTreeDecoration

問題

• クリスマスツリーのデコレーションをする
• N個の星飾りがあり、それぞれの色が与えられる
• 飾りと飾りはリボンで結ぶことができる
• 結ぶことができる飾りの番号のリストが与えられる
• できる限り異なる色で結びたい
• 同じ色で結ぶことになる最小の個数を求める

方針

• まずできる限り異なる色のものだけ結ぶ。union find木で記憶しておく
• そのあと同じ色のものを必要最小限だけ結ぶ(=木同士を接続する)
• 木の総数-1が答え
• 最小全域木らしい
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_640/ChristmasTreeDecoration.cpp

結果

o-- 132.62pts 337th/416 rating 1368 -> 1312 (-56)

div1勢は典型問題つよい。

http://togetter.com/li/755859