[AtCoder] ABC 126 C – Dice and Coin

2019年5月19日2019年5月20日

問題

方針

初期値においてどれだけ連続して表が出る必要があるかを考えます。

サイコロを振って出た目を \( i \) とします。次に、コインが連続で表が出る回数を \( t \) とすると、

\[ i \times 2^{t} \geq K \]

を満たす最小の \( 0 \) 以上の整数 \( t \) を求めます。\( t = 0 \) のときはコインを投げる必要がないということです。また、このときの \( t \) を \( t_i \) とすると、求める確率 \( p \) は、

\[ p = \sum_{ i = 1 }^{ n } \dfrac{1}{N \cdot 2^{t_i}}\]

となります。これは、サイコロの \( i \) が出る確率は等確率なので、\( \frac{1}{N} \) であり、コインが連続して表が出る確率は \( \frac{1}{2^{t_i}} \) であることから導けます。

コード

提出したコード

確率の計算

  int N, K;
  cin >> N >> K;
  vector<int> t;
  t.push_back(1);
  while (true) {
    int a = t[t.size() - 1];
    if (a > K) break;
    else {
      t.push_back(a * 2);
    }
  }
  double p = 0.0;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < t.size(); j++) {
      if (i * t[j] >= K) {
        double b = N * t[j];
        p += 1 / b;
        break;
      }
    }
  }
  printf("%.10f\n", p);