結果

問題 No.155 生放送とBGM
コンテスト
ユーザー d01phn
提出日時 2021-02-02 13:00:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 439 ms / 6,000 ms
コード長 2,128 bytes
コンパイル時間 1,578 ms
コンパイル使用メモリ 170,516 KB
実行使用メモリ 369,444 KB
最終ジャッジ日時 2024-06-29 23:40:02
合計ジャッジ時間 4,636 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define reps(i,n) for (int i = 1; i <= (n); ++i)
#define rrep(i,n) for (int i = (n) - 1; i >= 0; --i)
#define rreps(i,n) for (int i = (n); i > 0; --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
#define MP make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
using namespace std;
using ll = long long;
using P = pair<int,int>;

int str2int(string str) {
  int mm = (str[0] - '0') * 10 + (str[1] - '0');
  int ss = (str[3] - '0') * 10 + (str[4] - '0');
  return 60 * mm + ss;
}

const int N = 50, L = 300 * 60;

int n, l, s[N];

/* i曲目まででj曲選びk秒以内である場合の数 */
ll dp[N + 1][N + 1][L + 1];

double fact_inv(int n) {
  double res = 1;
  reps(i, n) res /= i;
  return res;
}

int main() {
  cin >> n >> l;
  l *= 60; // min -> s
  string str_s;
  rep(i, n) {
    cin >> str_s;
    s[i] = str2int(str_s);
  }

  int ssm = 0;
  rep(i, n) ssm += s[i];
  if (ssm <= l) {
    cout << n << endl;
    return 0;
  }

  rep(i, n + 1) rep(j, n + 1) rep(k, l + 1) dp[i][j][k] = 0;
  rep(k, l + 1) dp[0][0][k] = 1;

  rep(i, n) rep(j, n + 1) rep(k, l + 1) {
    dp[i + 1][j][k] += dp[i][j][k];
    if (j - 1 >= 0 && k - s[i] >= 0) dp[i + 1][j][k] += dp[i][j - 1][k - s[i]];
  }

  rep(i, n) rep(j, n + 1) rep(k, l + 1) {
    dp[i][j][k] = dp[n][j][k];
    if (j - 1 >= 0 && k - s[i] >= 0) dp[i][j][k] -= dp[i][j - 1][k - s[i]];
  }

  // rep(i, n) {
  //   printf("i = %d\n", i);
  //   rep(j, n + 1) {
  //     printf("dp[%d][%d][%d] = %lld\n", i, j, l, dp[i][j][l]);
  //     // rep(k, l + 1) printf("%lld ", dp[i][j][k]);
  //     // printf("\n");
  //   }
  // }

  double ans = 0;
  rep(i, n) rep(j, n) {
    if (l - s[i] - 1 < 0) ans += dp[i][j][l - 1] * fact_inv(n - 1) / fact_inv(j) / fact_inv(n - j - 1) * (j + 1) / n;
    else ans += (dp[i][j][l - 1] - dp[i][j][l - s[i] - 1]) * fact_inv(n - 1) / fact_inv(j) / fact_inv(n - j - 1) * (j + 1) / n;
    // printf("i = %d, j = %d, ans = %.9f\n", i, j, ans);
  }
  printf("%.9f\n", ans);
  return 0;
}
0