hotpepsiの練習帳

TCO12 Round 2B

22:00

Easy (300) BlurredDartboard

問題

• N分割されていて、それぞれ1～N点のダーツ盤がある。
• 一部の文字盤は汚れていて数値が読めない。
• 正確にどれでも当てられるとして、最低P点以上にできる回数を求める。

方針

• 読める部分の最大値と、読めない部分(Z個)の期待値を求めて、どちらかを使う二択
• 読める部分の最大値が期待値以上であれば、最大値だけで試行すればよい
• 期待値を使う場合は、Z個単位で試行するとZ×期待値のポイントが得られる
• Z×期待値未満のポイントについては場合わけが必要
• 読めない部分の小さい値から順番に取得すると考える
• それらの総和が残りのポイント以上ならOK
• ただし、最大値だけで試行したほうがよい場合がある
• https://github.com/firewood/topcoder/blob/master/tco_2012/BlurredDartboard.cpp

結果

o-- 150.03pt 616th rating 1368 -> 1414

300点ということで慎重に解いたら遅すぎた。でも正解なのはとても良い。