結果
問題 | No.155 生放送とBGM |
ユーザー | なお |
提出日時 | 2015-02-18 06:05:40 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 354 ms / 6,000 ms |
コード長 | 3,369 bytes |
コンパイル時間 | 1,478 ms |
コンパイル使用メモリ | 146,284 KB |
実行使用メモリ | 468,820 KB |
最終ジャッジ日時 | 2023-09-06 02:00:47 |
合計ジャッジ時間 | 4,566 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 326 ms
440,308 KB |
testcase_01 | AC | 354 ms
438,360 KB |
testcase_02 | AC | 269 ms
429,012 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 49 ms
220,700 KB |
testcase_05 | AC | 2 ms
7,632 KB |
testcase_06 | AC | 267 ms
468,820 KB |
testcase_07 | AC | 6 ms
20,012 KB |
testcase_08 | AC | 3 ms
11,716 KB |
testcase_09 | AC | 7 ms
26,032 KB |
testcase_10 | AC | 4 ms
13,856 KB |
testcase_11 | AC | 7 ms
26,180 KB |
testcase_12 | AC | 8 ms
30,112 KB |
testcase_13 | AC | 6 ms
24,000 KB |
testcase_14 | AC | 200 ms
425,664 KB |
ソースコード
#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; }