結果

問題 No.155 生放送とBGM
コンテスト
ユーザー なお
提出日時 2015-02-18 06:05:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 374 ms / 6,000 ms
コード長 3,369 bytes
コンパイル時間 1,336 ms
コンパイル使用メモリ 162,064 KB
実行使用メモリ 438,748 KB
最終ジャッジ日時 2024-06-23 21:03:09
合計ジャッジ時間 3,952 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = int(1e9+7);

int N,L;
int S[55];
ll dp[55][360*60+1];
ll T[55][55][360*60+1];

double fact[55];

double solve1(){
    dp[0][0] = 1; // [曲数][曲長]=通り数 のDP
    REP(i,N){
        int v = S[i];
        for(int j = i; j >= 0; j--)
            for(int k = v; k <= L; k++)
                dp[j+1][k] += dp[j][k-v];
    }

#ifdef _DEBUG
    REP(i,N) cerr << S[i] << " ";cerr << endl;
    REP(i,N){
        cerr << "i = " << i << endl;
        REP(j,400*60){
            if(dp[i][j]) cerr << j << " : " << dp[i][j] << endl;
        }
    }
#endif

    double res = 0;
    REP(i,N){
        int v = S[i];
        
        // j曲でk秒になる通り数は dp[j][k] 通り
        // i番目が最後にくるものだけほしいけどj曲にi番目が入ってるとは限らない

        // 要するにS[i]だけを使わないで曲長 < L になる通り数がほしい。
        // まじめにやるとN^3*18000のDP
        // まにあう気がする？ ギリギリまにあうっぽい

        // 戻すDPってなんぞや
        // (´･_･`)
        // dp[j][k] = Σ{i=0~N-1} dp[j-1][k-S[i]] だから
        // i番目を除くには、dp[j][k]のうちS[i]が足されてきたものすなわちdp[j-1][k-S[i]]を引く？
        // T[i][j][k] = dp[j][k] - T[i][j-1][k-S[i]]
        // dp[j-1][k-S[i]]じゃなくて T[i][j-1][k-S[i]] の理由がいまいちわからない。
        // S[i]が最後に足されていないといけないから、
        // それまでにもi番目が含まないような通り数じゃないといけないような気もする。

        REP(j,N){ // 曲数
            REP(k,L+v){
                T[i][j][k] = dp[j][k];
                if(k >= v && j > 0) T[i][j][k] -= T[i][j-1][k-v];
                if(k < L) res += T[i][j][k] * fact[j] * fact[N-1-j];
            }
        }

    }
    return res / fact[N];
}


ll dp2[55][55][300*60+1];
double solve2(){
    double res = 0;
    REP(i,N){   // i番目を除外
        dp2[i][0][0] = 1;
        REP(j,N){   // j番目の曲を足す
            if(i == j) continue;
            int v = S[j];
            for(int k = N; k > 0; k--){   // 曲数
                FOR(l,v,18001){
                    dp2[i][k][l] += dp2[i][k-1][l-v];
                }
            }
        }

        // i番目が先頭になる(N-1)!通り
        res += fact[N-1];
        FOR(k,1,N){     // 曲数
            REP(l,L){   // 曲長
                res += dp2[i][k][l] * fact[k] * fact[N-1-k];
            }
        }
    }

    return res / fact[N];
}

int main(){
    do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0);
    cin >> N >> L;
    L *= 60;

    int total = 0;
    REP(i,N){
        int min,sec;char d;
        cin >> min >> d >> sec;
        S[i] = min*60+sec;
        total += S[i];
    }
    if(total <= L){
        cout << N << endl;
        return 0;
    }
    fact[0] = 1;
    FOR(i,1,55) fact[i] = fact[i-1]*i;

    cout << fixed << setprecision(12) <<  solve1() << endl;

    return 0;
}
0