\(f(i)\) を、直近に出たサイコロの目が \(i\) であるときこれ以降に得られる給料の期待値とします。

まず、 \(i\) が出たので \(A_i\) 円を貰うことができます。これに次以降のサイコロによる収入を合わせると \(f(i)\) の値を求めることができます。次に出るサイコロの目 \(x\) で場合分けすることで解けます：

1. \(i \geq x\) のとき：操作はこれで終了します。よって、\(0\) です。

2. \(i \lt x\)のとき：これ以降もらえる給料の期待値は \(f(x)\) に等しいです。

サイコロの目は等確率で出るので、結局

\(\displaystyle f(i) = A_i + \frac{1}{N} (f(i + 1) + f(i + 2) + \dots + f(N) )\)

として求めることができます。\(f(i)\) を計算するのに必要なのは \(i + 1\) 以降についての \(f\) の値の総和なので、この値を 変数として管理しておくことで \(i\) の大きい方から順に \(f(i)\) を求めることができます。この時の計算量は \(O(N)\) です。

あとは、操作の最初に出た目を考えると、

\(\frac{1}{N} (f(1) + f(2) + \dots + f(N) )\)

が答えとなるので、これを計算すればよいです。全体での計算量も \(O(N)\) となります。

\(A_0 = 0\) を仮定すると、上記の \(f(i)\) の計算式で求めた \(f(0)\) が答えとなるので、実装が楽になります。