hotpepsiの練習帳

SRM 547

02:03

Div1 Easy (250) Pillars

問題

• 2本の柱があり、柱間の距離はwである。
• それぞれの柱の高さは、1からx、および、1からyのいずれかである。
• 柱の上端をまっすぐなロープで結ぶとき、ロープの長さの期待値を求める。

方針

• xとyのうち、低い方をa、高い方をbとして、高さの差で場合わけしてみる
• 高低差をdとする
• d=0(同じ高さ)になるのはa通り
• b側が高い場合、b側の一番低いケースの高さは1+d、一番高いケースの高さはmin(b, a+d)なので、(min(b, a+d) - (1+d) +1)通り
• a側が高い場合、a側の一番低いケースの高さは1+d、一番高いケースの高さはaなので、(a - (1+d) + 1)通り
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_547/Pillars.cpp

結果

o-- 120.31pt 270th rating 1352 -> 1382 (+30)

なんとかプラス点。