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) で実装してみる。 -> TLE で計算おわらず。 1.txt をローカルで計算したところ、113 秒かかった。 dp は、ゼロ要素がかなり多い。ループを全部まわすのでなく、必要なところだけを見るように変更してみる。 まずは、dp の 行数を、必要な数のみにする。また、各行での計算の開始位置を記録しておく。 また、降順で MS を並べ替えておく。 -> 1.txt の処理を 29 秒にまで短縮できた。 PyPy なら 6 秒切れるだろうか。。 -> 1.txt, 2.txt を PyPy3 で 3.5 sec で計算できたが、3.txt で TLE dp の計算を、整数でなく、float にしてみた。 ''' if sum(MS) <= L: return N MS.sort(reverse=True) 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.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.0] * L] dp[0][0] = 1.0 minsum = [L] * (N + 1) minsum[0] = 0 for msj in ms: k = len(dp) - 1 if minsum[k] + msj < L: dp.append([0.0] * L) else: k-= 1 threshold = L - msj for n in range(k, -1, -1): if minsum[n] >= threshold: continue msum = minsum[n] + msj if msum < minsum[n+1]: minsum[n+1] = msum dpn = dp[n] dpn_next = dp[n + 1] for newt, dpnt in enumerate(dpn[minsum[n]:-msj], msum): if dpnt: dpn_next[newt] += dpnt return dp if __name__ == '__main__': N, L, MS = read_data() print(solve(N, L, MS))