E - Playlist

[hxrxchang]

https://atcoder.jp/contests/abc323/tasks/abc323_e

問題概要

N曲のプレイリストがあって、それぞれの曲の長さが分かっている。X + 0.5秒後にプレイリストの1曲目がかかっている確率を求めよ。

解き方

xまでの時刻iまでの各時刻で、その時刻ちょうどに何かしら曲が終了する確率を求める。

func solve() {
    in := getInts()
    n, x := in[0], in[1]
    t := getInts()

    inv := modPow(n, MOD - 2, MOD)

    // dp[i]: 時刻iの瞬間に何かしらの曲がちょうど終了する確率
    dp := make([]int, x + 1)
    // 0秒には何もかかっていない、100%の確率で曲が終了しているといえるので1
    dp[0] = 1

    for i := 1; i <= x; i++ {
        for _, v := range t {
            if i - v >= 0 {
                dp[i] += mod(dp[i - v] * inv,  MOD)
                dp[i] = mod(dp[i], MOD)
            }
        }
    }

    ans := 0
    for i := 0; i <= x; i++ {
        if i + t[0] > x {
            ans += mod(dp[i] * inv, MOD)
            ans = mod(ans, MOD)
        }
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc323/submissions/54933288