まず、このゲームの最適な戦略を探す際に探索すべき範囲を絞り込んでいきます。

サイコロを振ったときに各面が出る確率や最終的な結果は途中経過に依存しないため、その時点の\(x\) の値のみに依存してサイコロを振るか否かを判断するような戦略のみを考えれば十分です。さらに、以下の2点を考慮すると、（ディーラーの戦略と同様に）ある非負整数\(M\) に対して\(x \lt M\) のときはサイコロを振り、そうでないときは振らないという戦略のみを考えれば十分であることもわかります。

• \(x\) の値が大きいほど、サイコロを振る判断をしたときに\(x\) が\(N\) を超えてしまう確率が大きい。
• \(x\) の値が大きいほど、サイコロを振らない判断をしたときに勝てる確率が大きい。

上記の\(M\) として意味があるのは\(0\) 以上\(N\) 以下の整数であるため、考えるべき戦略はたかだか\((N+1)\) 個です。よって、これらの戦略全てについて勝率を確認し、それらの中で最大のものを答えとすればよいです。

上記の戦略において\(M=k\) としたときに、最終的に\(x=i\) となる確率を\(p_{k} (i)\) と表すことにします。ディーラーの戦略は\(M=L\) の場合と同様であるため、最終的に\(y=i\) となる確率は\(p_{L} (i)\) で表されます。

上記の戦略において\(M=k\) とした場合の勝率は
\(\displaystyle s_{k} = \sum_{i = k}^{N} w(i) \times p_{k}(i)\)
です。ただし、任意の非負整数\(i\) に対し
\(\displaystyle w(i) = \left(\sum_{j=0}^{i-1} p_{L}(j)\right)+\left(\sum_{j=N+1} p_{L}(j)\right)\)
とします。公式解説にも記載されている通り、\(p_{L}\) は\(O(N)\) の計算量で計算できるため、\(w\) も\(O(N)\) の計算量で計算できます。

ここで、\(s_{k}\) の値をもとに\(s_{k+1}\) の値を計算することを考えます。例えば、\(k+D \lt N\) のときは下記の式を満たします。
\(\displaystyle s_{k+1} = s_{k} - w(k) \times p_{k}(k) + \frac{p_{k}(i)}{D} \times \sum_{i = k+1}^{k+D} w(i)\)
また、\(k \lt N\) かつ\(k+D \ge N\) のときは下記の式を満たします。
\(\displaystyle s_{k+1} = s_{k} - w(k) \times p_{k}(k) + \frac{p_{k}(i)}{D} \times \sum_{i = k+1}^{N} w(i)\)
よって、\(w\) の累積和を事前に計算しておけば、\(s_{k}\) から\(s_{k+1}\) を求める計算は\(O(1)\) の計算量で計算できます。

この問題の答えを求めるには\(N\) 以下の全ての非負整数\(i\) について\(s_{i}\) が求められれば十分であるため、この問題は\(O(N)\) の計算量で解くことができます。

また、\(s_{k}\) から\(s_{k+1}\) を直接求める方法の他に、数列\(t\) と\(0 \le L \le R \le N\) を満たす任意の整数の組\(L\) と\(R\) について、\(\sum_{i=L}^{R} w(i) t(i)\) の値が求められるような遅延評価セグメント木を使用する方法でも、この問題を解くことができます。

前者の方針の提出:
https://atcoder.jp/contests/abc342/submissions/50637533

後者の方針の提出:
https://atcoder.jp/contests/abc342/submissions/50632807