提出 #20466423

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

vector<double> dp0;
vector<double> dp1;
vector<bool> hole;

int main()
{
  int n, m, k;
  cin >> n >> m >> k;

  dp0.resize(n+1+m);
  dp1.resize(n+1+m);
  hole.resize(n+1);

  for (int i = 0; i < k; i++){
    int ak;
    cin >> ak;
    hole[ak] = true;
  }

  int ct = 0;
  for (int i = 0; i <= n; i++){
    if (hole[i]) ct++;
    else ct = 0;
    if (ct == m){
      cout << -1 << endl;
      return 0;
    }
  }
  
  // X = f(0)
  // g(i) = dp0(i) * X + dp1(i)
  double mm = (double) m;
  double sum0 = 0.0;
  double sum1 = 0.0;
  for (int i = n-1; i >= 0; i--){
    if (hole[i]){
      dp0[i] = 1.0;
      dp1[i] = 0.0;
    } else {
      dp0[i] = sum0 / mm;
      dp1[i] = sum1 / mm + 1.0;
    }
    sum0 += dp0[i] - dp0[i+m];
    sum1 += dp1[i] - dp1[i+m];
  }

  double ans = dp1[0] / (1 - dp0[0]);
  cout << fixed << setprecision(4) << ans << endl;
  return 0;
}

提出情報

ジャッジ結果