提出 #44016725

---

ソースコード 拡げる

/*
    Author: Nguyen Tan Bao
    Status: AC
    Idea:
        - Let E[i] be the expected number of steps from i to n (or passing n)
        => E[i] = 0 if i >= n
           E[i] = E[0] if i is one of numbers in A
           E[i] = 1/m * sum(1 + E[j]) (j = i+1 to i+m)
                = 1 + 1/m * sum(E[j])
        - The answer is E[0]
        - We can see that this transition is cyclic and we have to use another way to solve.
        - Let E[i] = k[i] * E[0] + b[i]. Solving the equation E[0] = k[0] * E[0] + b[0] leads to
        the answer.
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define ALL(a) a.begin(), a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define TRAV(x, a) for (auto &x : a)

using namespace std;
using ll = long long; using ld = double; 
using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>;
using cd = complex<ld>; using vcd = vector<cd>;

using vi = vector<int>; using vl = vector<ll>;
using vd = vector<ld>; using vs = vector<string>;
using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; // vector<pair>

template<class T> using min_pq = priority_queue<T, vector<T>, greater<T> >;
template<class T> inline int ckmin(T& a, const T& val) { return val < a ? a = val, 1 : 0; }
template<class T> inline int ckmax(T& a, const T& val) { return a < val ? a = val, 1 : 0; }
template<class T> void remDup(vector<T>& v) { sort(ALL(v)); v.erase(unique(ALL(v)), end(v)); }

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down
void setPrec(int x) { cout << fixed << setprecision(x); }

// TO_STRING
#define ts to_string
string ts(char c) { return string(1, c); }
string ts(const char* s) { return (string) s; }
string ts(string s) { return s; }
string ts(bool b) { return ts((int)b); }
template<class T> string ts(complex<T> c) { stringstream ss; ss << c; return ss.str(); }
template<class T> using V = vector<T>;
string ts(V<bool> v) {string res = "{"; FOR(i,0,SZ(v)-1) res += char('0'+v[i]); res += "}"; return res; }
template<size_t sz> string ts(bitset<sz> b) { string res = ""; FOR(i,0,SZ(b)-1) res += char('0'+b[i]); return res; }
template<class T, class U> string ts(pair<T,U> p);
template<class T> string ts(T v) { // containers with begin(), end()
    bool fst = 1; string res = "";
    for (const auto& x: v) { if (!fst) res += " "; fst = 0; res += ts(x); }
    return res;
}
template<class T, class U> string ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class T> void pr(T x) { cout << ts(x); }
template<class T, class ...U> void pr(const T& t, const U&... u) { pr(t); pr(u...); }
void ps() { pr("\n"); } // print w/ spaces
template<class T, class ...U> void ps(const T& t, const U&... u) { pr(t); if (sizeof...(u)) pr(" "); ps(u...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class T, class ...U> void DBG(const T& t, const U&... u) { cerr << ts(t); if (sizeof...(u)) cerr << ", "; DBG(u...); }
#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
        << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);

const ld PI = acos(-1.0);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const ld EPS = 1e-9;
const ll MODBASE = 1000000007LL;
const int INF = 0x3f3f3f3f;

const int MAXN = 100010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

struct P {
    ld k, x;
};

P e[MAXN], sum[MAXN]; // E[i] = k * E[0] + x

P operator +(P i,P j) {
    return {i.k + j.k, i.x + j.x};
} 

P operator -(P i,P j) {
    return {i.k - j.k, i.x - j.x};
}

P operator /(P i, ld j) {
    return {i.k / j, i.x / j};
} 

int n, m, k, a[MAXK], ok[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    FOR(i,0,n) ok[i] = 1;
    FOR(i,1,k) {
        cin >> a[i];
        ok[a[i]] = 0;
    }
    FORE(i,n-1,0) {
        // E[i] = 1/m * sum(1 + E[j]) (j = i+1 to i+m)
        //      = 1 + 1/m * sum(E[j])
        // sum[i] here is the suffix sum of E[i..n]

        if (ok[i]) e[i] = (sum[i+1] - sum[i+m+1]) / m + (P){0, 1};
        else e[i] = (P) {1, 0};
        sum[i] = sum[i+1] + e[i];
    }
    if (fabs(e[0].k - 1) < EPS) cout << -1;
    else {
        // E[0] = k * E[0] + x
        // E[0] = -x / (k - 1)
        ld res = -e[0].x / (e[0].k - 1);
        cout << fixed << setprecision(9) << res;
    }
    return 0;
}

提出情報

ジャッジ結果