以下でも \(\gamma _ k=(1+2 ^ {-p})^k-1\) と書くことにします。

---

まず、ディーラーの出目が \(y\) になる確率 \(p(y)\) の計算について考えます。

次のようなもらう DP

\[p(y)=\dfrac1D\sum _ {i=\min\lbrace0,y - D\rbrace} ^ {\min\lbrace y,L\rbrace}p(i)\]

を使って \(y=1,\ldots,L+D\) の順に計算を行います。

上の主張を用いることで、総和の計算では（これまでに求めた \(p(i)\) の値から定まる）真の総和からたかだか \(\gamma _ {2+\log _ 2D}\) の相対誤差が生じることがわかります。 この結果を \(D\) で割るため（\(D\) の値は浮動小数点数として正確に表すことができます）、計算によってたかだか \(\gamma _ {3+\log _ 2D}\) の相対誤差が生じます。

\(p(i)\ (\min\lbrace0,y - D\rbrace\leq i\lt\min\lbrace y,L\rbrace)\) にたかだか \(\gamma _ k\) の相対誤差がある場合について考えると、上の補題の証明と同様にして \(p(y)\) の相対誤差が \(\gamma _ {k+3+\log _ 2D}\) で上から抑えられます。

これを用いると、\(p(y)\) の計算結果は真の \(p(y)\) からたかだか \(\gamma _ {y(3+\log _ 2D)}\) の相対誤差があります。

---

次に、自分の出目の合計が \(x\) である状態から勝つ確率 \(q(x)\) の計算について考えます。

次のようなもらう DP

\[q(x)=\max\left\lbrace\sum _ {y=\min\lbrace i,L\rbrace} ^ {\min\lbrace i,L+D\rbrace}p(y)+\sum _ {y=\min\lbrace N,L+D\rbrace+1} ^ {L+D}p(y),\dfrac1D\sum _ {i=x+1} ^ {\min\lbrace N,x+D\rbrace}q(i)\right\rbrace\]

を使って \(x=N,N-1,\ldots,1,0\) の順に計算を行います。

上の主張を用いることで、各総和の計算では（これまでに求めた \(p(i),q(i)\) の値から定まる）真の総和からたかだか \(\gamma _ {2+\log _ 2D}\) の相対誤差が生じることがわかります。

前者はそれらの和、後者はそれを \(D\) で割ったものであるので、この計算によってたかだか \(\gamma _ {3+\log _ 2D}\) の相対誤差が生じます。

\(p(y)\) の計算結果にはたかだか \(\gamma _ {y(3+\log _ 2D)}\) の相対誤差があったのでした。 よって、前者の真の値に対する相対誤差はたかだか \(\gamma _ {(L+D+1)(3+\log _ 2D)}\) と示せます。

よって、\(q(k)\) の真の値に対する相対誤差はたかだか \(\gamma _ {(L+D+1+N-k)(3+\log _ 2D)}\) です。

以上より、\(q(0)\) の計算結果に含まれる真の値からの相対誤差はたかだか \(\gamma _ {(L+D+N+1)(3+\log _ 2D)}\leq1.4\times10 ^ {-9}\) となります。

出力の際にたかだか \(5\times10 ^ {-7}\) の相対誤差が生じるため、以下のコードで AC が得られることがわかりました。

#include <iostream>
#include <functional>
#include <ranges>
#include <algorithm>
#include <iomanip>
#include <atcoder/segtree>

int main() {
    using namespace std;
    // 区間和取得のセグメント木
    using segment_tree = atcoder::segtree<double, plus<>{}, [] { return 0; }>;

    unsigned N, L, D;
    cin >> N >> L >> D;

    // ディーラーの出目が y になる確率 p(y)
    segment_tree dealer_p(L + D + 1);
    dealer_p.set(0, 1); // p(0) = 1
    for (const auto i : views::iota(1U, L + D + 1))
        if (const auto lower{i - min(i, D)}, upper{min(i, L)}; lower < upper)
            // p(i) = ∑_{y=max(0,i-D)}^{min(i,L)} p(y)
            dealer_p.set(i, dealer_p.prod(lower, upper) / D);

    // 自分の出目が x のところから勝てる確率 q(x)
    segment_tree my_win(N + 1);
    for (const auto i : views::iota(0U, N + 1) | views::reverse)
        // q(i) = max(サイコロを振らない, サイコロを振る)
        //      = max(∑_{min(L,i)≤y≤min(L+D,i)} p(y) + ∑_{min(N,L+D)+1≤y≤L+D} p(y), ∑_{x=i+1}^{min(N,i+D)} q(x))
        my_win.set(i, max(dealer_p.prod(min(L, i), min(L + D, i)) + dealer_p.prod(min(N, L + D) + 1, L + D + 1), my_win.prod(i + 1, min(N, i + D) + 1) / D));

    cout << setprecision(6) << my_win.get(0) << endl;

    return 0;
}