結果

問題 No.155 生放送とBGM
コンテスト
ユーザー rpy3cpp
提出日時 2015-06-03 17:11:43
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,128 bytes
コンパイル時間 74 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 39,204 KB
最終ジャッジ日時 2024-07-06 13:54:13
合計ジャッジ時間 14,578 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

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):
    '''
    f[n]: L秒で n+1 曲が流れる順列の数 として、
    x = sum((n+1) * f[n] for n in range(N))/N! を求めたい。
    f[i, n]: MS[i] が 最後の曲で、L秒で n+1 曲が流れる N 曲の順列の数とすると、
    f[n] = sum(f[i,n] for i in range(N))
    g[i, n]: MS[i] が 最後の曲で、L秒で n+1 曲が流れる、n 曲の選び方（組み合わせ）の数とすると、
    f[i, n] = g[i, n] * n! * (N-n-1)!
    g[n] = sum(g[i, n] for i in range(N)) とすると、
    x = sum(g[n] * (n + 1) * n! * (N - n -1)! / N! for n in range(N))
      = sum(g[n] / nCb(N, n+1) for n in range(N))
    h[i, n, t]: MS[i] を使わずに、n曲の合計の長さが、t秒となる n 曲の選び方（組み合わせ）の数とすると、
    g[i, n] = sum(h[i, n, t] for t in range(L-MS[i], L))
    h[i, n, t] は、動的計画法を使い、ナップサック問題を解くときの要領で、求めることができる。
    dp[i, j, n, t]: MS[i] を使わず、MS[:j]までを使った時に、n曲の合計がt秒となるn曲の組み合わせの数
    すると、
    h[i, n, t] = dp[i, N, n, t]
    dp についての漸化式は、
    dp[i, j+1, n, t] = dp[i, j, n, t] + dp[i, j, n-1, t-MS[j]]
    dp[i, 0, 0, 0] = 1, dp[i, 0, 0, t] = 0 (t>=1)
    h[i, n, t] は、O(L*N^2) の計算量で求めることができる。
    これを、0 <= i < N について繰り返して、h[] -> g[] -> f[] と順次計算すれば、
    f[n] を、O(L*N^3)の計算量で求めることができる。
    L = 300*60, N = 50 であるから、18000*125000 = 18*125*10^6 = 9*250*10^6=2.25*10^9
    6 sec で計算するのは厳しい。
    計算量を落とす方法を考える。
    dp[i, j, n, t] と、h[i+1, j, n, t] は、i > j であれば、完全に一致する。
    この計算の重複を省きたい。
    MSについて、分割統治法を適用すれば、O(N) を O(log(N)) に落とせないだろうか。
    が、とりあえず、O(L*N^3) で実装してみる。
    '''
    if sum(MS) <= L:
        return N
    g = get_g(N, L, MS)
    return sum(gi / nCb(N, n + 1) for n, gi in enumerate(g))
    
def get_g(N, L, MS):
    g = [0] * N
    for i, msi in enumerate(MS):
        ms = MS[:i] + MS[i+1:]
        h = get_h(N, L, ms)
        lmsi = max(L - msi, 0)
        for n, hn in enumerate(h):
            g[n] += sum(hn[lmsi:])
    return g

def get_h(N, L, ms):
    dp = [[0] * L for n in range(N)]
    dp[0][0] = 1
    for j, msj in enumerate(ms):
        for n in range(j, -1, -1):
            dpn = dp[n]
            for t, dpnt in enumerate(dpn[:-msj]):
                if dpnt:
                    dp[n + 1][t + msj] += dpnt
    return dp

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