結果

問題 No.155 生放送とBGM
ユーザー なおなお
提出日時 2015-02-18 04:49:21
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,089 ms / 6,000 ms
コード長 2,467 bytes
コンパイル時間 1,177 ms
コンパイル使用メモリ 145,816 KB
実行使用メモリ 367,148 KB
最終ジャッジ日時 2023-09-06 01:59:46
合計ジャッジ時間 14,189 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,985 ms
367,148 KB
testcase_01 AC 2,073 ms
367,016 KB
testcase_02 AC 2,089 ms
367,124 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 489 ms
180,000 KB
testcase_05 AC 2 ms
5,700 KB
testcase_06 AC 1,747 ms
311,324 KB
testcase_07 AC 5 ms
14,304 KB
testcase_08 AC 2 ms
7,868 KB
testcase_09 AC 10 ms
19,984 KB
testcase_10 AC 4 ms
12,260 KB
testcase_11 AC 10 ms
19,992 KB
testcase_12 AC 12 ms
22,944 KB
testcase_13 AC 6 ms
14,960 KB
testcase_14 AC 1,665 ms
337,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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];

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番目が最後にくるものだけほしい?

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

        // 戻すDPってなんぞや
        // (´･_･`)

    }
    return 0;
}
*/

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) <<  solve2() << endl;

    return 0;
}
0