結果

問題 No.155 生放送とBGM
コンテスト
ユーザー rpy3cpp
提出日時 2015-06-03 22:06:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,707 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 267,160 KB
最終ジャッジ日時 2024-07-06 13:59:28
合計ジャッジ時間 6,099 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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