2017/10/11の精進

昨日は家に帰ってすぐ寝てしまって更新できなかった(老人)

・yukicoder No.155 生放送とBGM

戻すDPの練習

まずLが曲の長さの和以上の場合、全ての曲が1回以上再生されることは明らかなので、Lは曲の長さの和未満とする

期待値の線形性(和の期待値は期待値の和)より、生放送中にi曲目が再生される確率がわかればその和で求めたい「生放送で流れる曲数の期待値」がわかる

方針としては

dp[i][j]=N曲からi曲選んで、長さの和がjとなるような組み合わせの数

を計算し、戻すDPで1つ戻して

dp2[i][j]=曲x以外のN-1曲からi曲選んで、長さの和がjとなるような組み合わせの数

を計算

曲の順列はN!通りあり、そのうち曲xが生放送で流れるのは、曲xより前にあるi曲の長さの和がj(<L)であるものなので(dp2[i][j]*i!*(N-i-1)!の和)通りになり、これで確率がわかった

おしまい