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): ''' 小手先の対応では無理っぽいので、分割統治法を実装。 また、dp の各行での計算の開始位置に加えて、終了位置も記録するようにした。 値の書き換えを、リスト内包表記に置き換えた。 ''' if sum(MS) <= L: return N MS.sort(reverse=True) dp = [[0] * L] dp[0][0] = 1 lower = [L] * (N + 1) upper = [0] * (N + 1) lower[0] = 0 g = get_g(dp, lower, upper, MS) print(g) return sum(gi / nCb(N, n + 1) for n, gi in enumerate(g)) def get_g(dp, lower, upper, ms): ''' 引数: dp: 途中まで作成済みの dp table(二次元リスト) lower: dp の各行の0でない要素の開始位置を収めたリスト upper: dp の各行の0でない要素の終了位置を収めたリスト ms: まだ使っていない MS の部分列 返り値: g: 完成した g[n] を格納した一次元リスト ''' mid = len(ms) // 2 if mid == 0: lmsi = max(len(dp[0]) - ms[0], 0) return [sum(dpi[lmsi:]) for dpi in dp] ms0 = ms[:mid] ms1 = ms[mid:] dp0, lower0, upper0 = extend_dp(dp, lower, upper, ms0) dp1, lower1, upper1 = extend_dp(dp, lower, upper, ms1) g0 = get_g(dp0, lower0, upper0, ms1) g1 = get_g(dp1, lower1, upper1, ms0) return [g0i + g1i for g0i, g1i in zip(g0, g1)] def extend_dp(dp_original, lower_original, upper_original, ms): dp = [dpi[:] for dpi in dp_original] lower = lower_original[:] upper = upper_original[:] L = len(dp[0]) for msj in ms: k = len(dp) - 1 if lower[k] + msj < L: dp.append([0] * L) else: k-= 1 threshold = L - msj for n in range(k, -1, -1): if lower[n] >= threshold: continue new_lower = lower[n] + msj if new_lower < lower[n+1]: lower[n+1] = new_lower new_upper = min(upper[n] + msj, L-1) if new_upper > upper[n+1]: upper[n+1] = new_upper dpn = dp[n] dpn_next = dp[n + 1] dpn_next[new_lower:new_upper+1] = [a + b for a, b in zip(dpn_next[new_lower:new_upper+1], dpn[lower[n]:upper[n]+1])] return dp, lower, upper if __name__ == '__main__': N, L, MS = read_data() print(solve(N, L, MS))