Shuffle (UVa 11826)
問題
仕事の行き帰りに音楽を聞くことにした。ミュージックプレイヤーにはシャッフルモードが付いていて、1回シャッフルすると全ての曲を流すか、プレイを止めるまでは同じ曲は流れない。また、プレイを止めた後にもう一度シャッフルした場合、一度でも流したことがある曲は流してない曲の2倍の確率で選ばれる。
全ての曲が1分で終わると仮定したとき、曲の数N、会社に行くのにかかる時間の確率、帰るのにかかる時間の確率が与えるので全ての曲を聞くのにかかる日数の期待値を求めよ。
1<=N<=75
0<=行き・帰りにかかる時間<=30
解法
まず、probability[n][rest][q][next]を計算する。これはこのセッションで聞いてない曲がn個存在し、今まで一度も聞いてない曲がrestだけ存在し、会社(家)までに着く時間の残りがq分の場合に、まだ聞いてない曲をちょうどnext個聞く確率である。これはdpによってO(N^2q^2)で求めることができる。
次にsumProbability[n][rest][qsum][next]を計算する。これは[0, qsum]の区間のprobability[n][rest][q][next]の総和を表す。
最後に各テストケースでdp[0][rest],dp[1][rest]を求める。dp[0][rest]は行き、dp[1][rest]は帰りにまだ聞いてない曲がrestだけある場合に全ての曲を聞き終えるまでにかかる日数の期待値である。dp[0][rest]は[0, rest)のdp[1][rest]とsumProbabilityを使えばO(rest)で計算できる。restが減らずにループする場合があるがその場合は方程式を解くか、無限等比級数の和の公式を用いて計算すれば良い。
全体でO(TN^2+N^2q^2)で計算可能。
