結果

問題 No.155 生放送とBGM
ユーザー rpy3cpprpy3cpp
提出日時 2015-06-03 18:13:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,097 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 266,360 KB
最終ジャッジ日時 2024-07-06 13:55:14
合計ジャッジ時間 12,645 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,593 ms
240,616 KB
testcase_01 AC 1,719 ms
245,952 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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) で実装してみる。

    -> TLE で計算おわらず。
    1.txt をローカルで計算したところ、113 秒かかった。
    
    dp は、ゼロ要素がかなり多い。ループを全部まわすのでなく、必要なところだけを見るように変更してみる。
    まずは、dp の 行数を、必要な数のみにする。また、各行での計算の開始位置を記録しておく。
    また、降順で MS を並べ替えておく。
    -> 1.txt の処理を　29 秒にまで短縮できた。
    PyPy なら 6 秒切れるだろうか。。
    '''
    if sum(MS) <= L:
        return N
    MS.sort(reverse=True)
    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]
    dp[0][0] = 1
    minsum = [L] * (N + 1)
    minsum[0] = 0
    for msj in ms:
        k = len(dp) - 1
        if minsum[k] + msj < L:
            dp.append([0] * L)
        else:
            k-= 1
        threshold = L - msj
        for n in range(k, -1, -1):
            if minsum[n] >= threshold:
                continue
            msum = minsum[n] + msj
            if msum < minsum[n+1]:
                minsum[n+1] = msum
            dpn = dp[n]
            dpn_next = dp[n + 1]
            for newt, dpnt in enumerate(dpn[minsum[n]:-msj], msum):
                if dpnt:
                    dpn_next[newt] += dpnt
    return dp

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