結果

問題 No.302 サイコロで確率問題 (2)
コンテスト
ユーザー yuppe19 😺
提出日時 2018-04-25 13:21:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 6,000 ms
コード長 1,113 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 78,636 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 21:01:35
合計ジャッジ時間 1,799 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;
using decimal = long double;

double solve1(i64 n, i64 l, i64 r) {
  vector<double> dp(6*n+1);
  dp[0] = 1;
  for(int i=0; i<n; ++i) {
    vector<double> ndp(6*n+1);
    for(int summ=i; summ<=6*i; ++summ) {
      if(dp[summ] < 1e-15) { continue; }
      for(int curr=1; curr<=6; ++curr) {
        ndp[summ+curr] += dp[summ] / 6;
      }
    }
    dp = ndp;
  }
  double res = 0;
  for(i64 i=l; i<=r; ++i) {
    res += dp[i];
  }
  return res;
}

decimal f(decimal x) {
  return (1 + erfl(x / sqrtl(2))) / 2;
}

decimal solve2(i64 n, i64 l, i64 r) {
  decimal u = decimal(7)  * n / 2,
          v = decimal(35) * n / 12,
          deno = sqrtl(v),
          half = decimal(1) / 2;
  return f((decimal(r) + half - u) / deno)
       - f((decimal(l) - half - u) / deno);
}

int main(void) {
  i64 n, l, r; scanf("%lld%lld%lld", &n, &l, &r);
  l = max(n, l);
  r = min(6*n, r);
  double res;
  if(n < 5000) {
    res = solve1(n, l, r);
  } else {
    res = solve2(n, l, r);
  }
  printf("%.15lf\n", res);
  return 0;
}
0