import math def read_data(): N, L = map(int, input().split()) Ss = list(input().split()) MS = [] for s in Ss: mm, ss = map(int, s.split(':')) MS.append(mm * 60 + ss) return N, L * 60, MS def nCb(n, b): return math.factorial(n)//math.factorial(b)//math.factorial(n-b) def solve(N, L, MS): ''' f[n]: L秒で n+1 曲が流れる順列の数 として、 x = sum((n+1) * f[n] for n in range(N))/N! を求めたい。 f[i, n]: MS[i] が 最後の曲で、L秒で n+1 曲が流れる N 曲の順列の数とすると、 f[n] = sum(f[i,n] for i in range(N)) g[i, n]: MS[i] が 最後の曲で、L秒で n+1 曲が流れる、n 曲の選び方(組み合わせ)の数とすると、 f[i, n] = g[i, n] * n! * (N-n-1)! g[n] = sum(g[i, n] for i in range(N)) とすると、 x = sum(g[n] * (n + 1) * n! * (N - n -1)! / N! for n in range(N)) = sum(g[n] / nCb(N, n+1) for n in range(N)) h[i, n, t]: MS[i] を使わずに、n曲の合計の長さが、t秒となる n 曲の選び方(組み合わせ)の数とすると、 g[i, n] = sum(h[i, n, t] for t in range(L-MS[i], L)) h[i, n, t] は、動的計画法を使い、ナップサック問題を解くときの要領で、求めることができる。 dp[i, j, n, t]: MS[i] を使わず、MS[:j]までを使った時に、n曲の合計がt秒となるn曲の組み合わせの数 すると、 h[i, n, t] = dp[i, N, n, t] dp についての漸化式は、 dp[i, j+1, n, t] = dp[i, j, n, t] + dp[i, j, n-1, t-MS[j]] dp[i, 0, 0, 0] = 1, dp[i, 0, 0, t] = 0 (t>=1) h[i, n, t] は、O(L*N^2) の計算量で求めることができる。 これを、0 <= i < N について繰り返して、h[] -> g[] -> f[] と順次計算すれば、 f[n] を、O(L*N^3)の計算量で求めることができる。 L = 300*60, N = 50 であるから、18000*125000 = 18*125*10^6 = 9*250*10^6=2.25*10^9 6 sec で計算するのは厳しい。 計算量を落とす方法を考える。 dp[i, j, n, t] と、h[i+1, j, n, t] は、i > j であれば、完全に一致する。 この計算の重複を省きたい。 MSについて、分割統治法を適用すれば、O(N) を O(log(N)) に落とせないだろうか。 が、とりあえず、O(L*N^3) で実装してみる。 ''' if sum(MS) <= L: return N g = get_g(N, L, MS) return sum(gi / nCb(N, n + 1) for n, gi in enumerate(g)) def get_g(N, L, MS): g = [0] * N for i, msi in enumerate(MS): ms = MS[:i] + MS[i+1:] h = get_h(N, L, ms) lmsi = max(L - msi, 0) for n, hn in enumerate(h): g[n] += sum(hn[lmsi:]) return g def get_h(N, L, ms): dp = [[0] * L for n in range(N)] dp[0][0] = 1 for j, msj in enumerate(ms): for n in range(j, -1, -1): dpn = dp[n] for t, dpnt in enumerate(dpn[:-msj]): if dpnt: dp[n + 1][t + msj] += dpnt return dp if __name__ == '__main__': N, L, MS = read_data() print(solve(N, L, MS))