hotpepsiの練習帳

SRM 621

01:52

Div1 Easy (250) RadioRange

問題

• 座標(0,0)に放送局がある
• いくつかの街の中心座標と半径が与えられる
• それぞれの街について、放送局の電波が完全に届かないか、または、街の中全てがカバーされていればgood
• 放送局の半径を0以上Z以下の乱数で選ぶとき、全ての街がgoodとなる確率を求める

方針

• 街が存在する範囲をbad rangeとして、0以上Z以下で、bad rangeでない部分を数える
• 開始位置でソートする
• 現在地を0からはじめて、前のbad rangeの終点から、次のbad rangeの始点までをgoodとして足していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_621/RadioRange.cpp

結果

o-- +1 152.62 + 50 = 202.62pts 254th/763 rating 1585 -> 1633 (+48)

範囲外のをきちんとはじくのが意外と面倒。最初に0からZまでの範囲にしておくと少し楽。

写経撃墜でhighest更新。瞬間的にcountry rankの100位に入った。感激。

http://togetter.com/li/669609