結果
問題 | No.1478 Simple Sugoroku |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:56:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 1,997 bytes |
コンパイル時間 | 3,239 ms |
コンパイル使用メモリ | 170,552 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-02 23:39:03 |
合計ジャッジ時間 | 6,235 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <iostream>#include <string>#include <cmath>#include<algorithm>#include<stack>#include<queue>#include<map>#include<set>#include<iomanip>#include<bitset>#define _USE_MATH_DEFINES#include <math.h>#include <functional>#include<complex>#include<cassert>#include<random>using namespace std;#include<atcoder/all>using namespace atcoder;#define rep(i,x) for(ll i=0;i<x;i++)#define repn(i,x) for(ll i=1;i<=x;i++)typedef long long ll;typedef pair<ll, ll> P;const ll INF = 1e17;const ll MAX = 4000001;const long double eps = 1E-14;ll max(ll a, ll b) {if (a > b) { return a; }return b;}ll min(ll a, ll b) {if (a > b) { return b; }return a;}ll gcd(ll a, ll b) {if (b == 0) { return a; }if (a < b) { return gcd(b, a); }return gcd(b, a % b);}ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}struct edge {ll id;ll fr;ll to;ll d;};using mint = modint;typedef vector<ll> vll;typedef vector <vector<ll>> vvll;typedef vector<vector<vector<ll>>> vvvll;typedef vector<mint> vmint;typedef vector<vector<mint>> vvmint;typedef vector<vector<vector<mint>>> vvvmint;vmint f, finv, inv;void cominit(ll N) {ll MOD = modint::mod();//デフォルトが998244353に注意f.assign(N + 1, 1);finv.assign(N + 1, 1);inv.assign(N + 1, 1);inv[1] = 1;repn(i, N) {f[i] = f[i - 1] * i;if (i > 1)inv[i] = -inv[MOD % i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}mint com(ll a, ll b) {if (a < 0 || b < 0 || a < b) { return 0; }return f[a] * finv[b] * finv[a - b];}/////////////////////////////////////int main() {cout << fixed << setprecision(10);ll N, M;cin >> N >> M;vll B(M);rep(i, M)cin >> B[i];double ans = INF;ll sum = 0;for (ll i = M - 1; i >= 0; i--) {sum += N - B[i];double now = (double)(M) / (double)(M-i) +(double)(sum) / (double)(M - i);now += B[0] - 1;//cout << now << endl;ans = min(ans, now);}ans = min(ans, (double)(N - 1));cout << ans << endl;}