TCO Qualifier1 - simezi

UTPCの懇親会に参加していたので本番は不参加。エアQual1してみた。
Easy 226.29 / Medium 451.43 / Hard -

うそつきがx人だとする⇒
嘘つき：xより大きい数字を言っている人
正直者：x以下の数字を言っている人
⇔
なので、xより大きい数字を言っている人が丁度x人居ることが必要十分

音楽プレイヤーが長さl[i]の曲をランダムに再生する（重複あり）。
T+0.5秒後にそれぞれの曲が鳴っている確率を求める。

i秒立った瞬間に曲が終わっている確率をdp[i]としてみる。
するとdp[i+新しい曲jの長さ]+=dp[j]/n
ここで、i+新しい曲jの長さがTを超えているときはT+0.5秒後にその曲が鳴っている場合なので、その曲の確率にdp[i]/nを足してやる。

場合わけしまくろうとしたがスパゲッティになりすぎて結局解けなかった。
他人のコードを見るとどうも探索してるぽい。
QualなのでDiv1のMedium++くらいの難易度のハズなので一眠りしたらコード読んで通す。

……と思ったが本番でもかなり通してる人少なげなのでeditorial待ち。