問題概要
$1$ 以上 $6$ 以下の整数の目が等確率で出るダイスを使ったゲームを考える．ゲームは最大 $N$ ラウンドからなる．各ラウンドではサイコロを一回振り，その出目を $X$ とする．その後行えることは，
- 現在が $N$ ラウンド目なら，$X$ をゲームのスコアとしてゲームを終了する
- そうでないとき，スコアを $X$ としてゲームを終了するか，次のラウンドに進むかを選択する
である．
$N$ が与えられる．スコアの期待値を最大化するようにプレイしたとき，その期待値を求めよ．
制約
- $1 \leq N \leq 100$
解法
各 $N$ に対する答えを $E( N )$ と書くことにします．
問題について理解を深める上で，まずは簡単なケースについて考えてみましょう．この問題で最も簡単なケースとは，$N = 1$ の場合です．この場合は単純にダイスを一回振った場合の出目の平均値ですから，$1$ から $6$ の和を $6$ で割って，$$E( 1 ) = \frac{ \sum_{ i = 1 }^{ 6 } }{ 6 } = 3.5$$ となります*1．
では，$2$ 以上の $N$ についてはどうなるでしょうか．こちらの場合，出目 $X$ に対して，スコアとして $X$ を採用するか，残りの $N - 1$ ラウンドに賭けるかの選択ができます．これは，
- $X$ をスコアにする
- $E( N - 1 )$ をスコアにする
という選択肢を提示されていることになります．これはどういうことかというと，
- 確実に $X$ が排出されるガチャ
- 平均値が $E( N - 1 )$ となるように排出されるガチャ
の 2 つを提示されている状況です．平均がよい方を採用した方が得ですから，出目 $X$ が固定された状況での最適な期待値とは，$$\max( X, E( N - 1 ) )$$ です．
これで出目別の期待値は分かりましたが，出目が確定していない状態での期待値はどうなるでしょうか．唐突ですが，期待値の線形性というのがあります．リンク先にもありますが，よく出てくるキーワードで「和の期待値は期待値の和」というのがあります．これを認めるならば，各出目ごとの期待値の和を取れば，欲しかった値が求まります．出目が $X$ だったときの期待値は先程のように $\max( X, E( N - 1 ) )$ で，その出目が出る確率は $\frac 1 6$ なので，出目全てについて和を取れば，$$E( N ) = \sum_{ i = 1 }^6 \frac{\max( i, E( N - 1 ) ) } 6$$ となります．
これで，$E( k - 1 )$ の値を使って $E( k )$ の値を求める方法が分かったことになるので，$E( 2 )$ から順に値を求める動的計画法的なことをすることで $E( N )$ を求めることができます．
このアルゴリズムは各 $i$ ($2 \leq i \leq N$) に対して定数回の算術演算を行うので，$\Theta( N )$ 時間で動作します．
コード
int main() { cin.tie( nullptr ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N ); static double dp[ 128 ]; // dp[ i rounds ] := expected value dp[1] = 3.5; REP( i, 2, N + 1 ) { REP( j, 1, 7 ) { dp[i] += max< double >( j, dp[ i - 1 ] ); } dp[i] /= 6; } cout << dp[N] << endl; return 0; }
*1:こんなことを考えなくてもサンプルを見れば一発ではあるのですが……
