結果

問題 No.155 生放送とBGM
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-03 22:44:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,094 ms / 6,000 ms
コード長 2,091 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 267,396 KB
最終ジャッジ日時 2024-07-06 14:01:31
合計ジャッジ時間 6,315 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 705 ms
260,224 KB
testcase_01 AC 743 ms
260,568 KB
testcase_02 AC 2,094 ms
267,396 KB
testcase_03 AC 34 ms
52,292 KB
testcase_04 AC 119 ms
89,472 KB
testcase_05 AC 35 ms
52,224 KB
testcase_06 AC 121 ms
158,976 KB
testcase_07 AC 39 ms
60,584 KB
testcase_08 AC 37 ms
58,368 KB
testcase_09 AC 45 ms
67,840 KB
testcase_10 AC 37 ms
58,496 KB
testcase_11 AC 45 ms
70,272 KB
testcase_12 AC 49 ms
75,248 KB
testcase_13 AC 41 ms
61,568 KB
testcase_14 AC 623 ms
264,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import zip_longest
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):
    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)
    return sum(gi / nCb(N, n + 1) for n, gi in enumerate(g))

def get_g(dp, lower, upper, ms):
    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_longest(g0, g1, fillvalue=0)]

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))
0