はじめに、\(y=i\) となる確率 \(p[i]\) を求めましょう。これは動的計画法で求めることが可能です。

具体的には、\(\mathrm{p}[0]=1\) からはじめて、\(i=0,1,\ldots,l-1\) について \(\mathrm{p}[i+1], \ldots,\mathrm{p}[i+D]\) に \(\frac{\mathrm{p}[i]}{D}\) を加算すればよいです。これは imos 法により高速に行えます。または、貰う DP だと思えば累積和により処理することもできます。

次に、\(x=i\) で終える場合の勝率 \(q[i]\) を求めましょう。これは先ほど求めた \(p[j]\) の累積和から計算できます。

最後に、\(x=i\) の状態のときの勝率 \(r[i]\)を求めましょう。サイコロを振る場合と振らない場合で場合分けすれば、

\[r[i] = \max(q[i], \frac{1}{D}\sum_{j=i+1}^{i+D}r[j])\]

という式が成り立つので、\(i\) の降順に \(r\) を求めることが出来ます。最終的に得られる \(r[0]\) が答えとなります。