結果

問題 No.155 生放送とBGM
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-03 23:09:22
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 1,151 ms / 6,000 ms
コード長 2,114 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 87,104 KB
実行使用メモリ 271,016 KB
最終ジャッジ日時 2023-09-20 19:04:54
合計ジャッジ時間 6,551 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 814 ms
264,864 KB
testcase_01 AC 817 ms
265,876 KB
testcase_02 AC 1,151 ms
271,016 KB
testcase_03 AC 77 ms
71,240 KB
testcase_04 AC 142 ms
86,168 KB
testcase_05 AC 75 ms
71,448 KB
testcase_06 AC 157 ms
159,020 KB
testcase_07 AC 79 ms
75,468 KB
testcase_08 AC 76 ms
74,956 KB
testcase_09 AC 81 ms
75,464 KB
testcase_10 AC 76 ms
75,188 KB
testcase_11 AC 80 ms
75,364 KB
testcase_12 AC 80 ms
75,544 KB
testcase_13 AC 76 ms
75,056 KB
testcase_14 AC 670 ms
270,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

from itertools import zip_longest
from math import factorial

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 solve(N, L, MS):
    if sum(MS) <= L:
        return N
    MS.sort(reverse=False)
    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 * factorial(n+1) * factorial(N-n-1) for n, gi in enumerate(g)) / factorial(N)

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]
            end = min(upper[n] + 1, threshold)
            for newt, dpnt in enumerate(dpn[lower[n]:end], new_lower):
                if dpnt:
                    dpn_next[newt] += dpnt
    return dp, lower, upper

if __name__ == '__main__':
    N, L, MS = read_data()
    print(solve(N, L, MS))
0