結果

問題 No.155 生放送とBGM
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-03 22:52:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,074 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 86,932 KB
実行使用メモリ 158,668 KB
最終ジャッジ日時 2023-09-20 19:04:22
合計ジャッジ時間 3,051 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 72 ms
71,256 KB
testcase_04 RE -
testcase_05 AC 73 ms
71,268 KB
testcase_06 AC 152 ms
158,668 KB
testcase_07 AC 76 ms
75,504 KB
testcase_08 AC 74 ms
75,312 KB
testcase_09 RE -
testcase_10 AC 76 ms
75,320 KB
testcase_11 AC 79 ms
75,332 KB
testcase_12 AC 79 ms
75,440 KB
testcase_13 RE -
testcase_14 RE -
権限があれば一括ダウンロードができます

ソースコード

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]
            for newt, dpnt in enumerate(dpn[lower[n]:upper[n]+1], 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