Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 266 E問題 Throwing the Die

AtCoder ABC266 ABC E問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

正多面体のダイスがあり, このダイスを振ると 1,2,3,4,5,6 のうちランダムで1つである. このダイスを用いて, 以下を考える.

  • ダイスの出目をスコアにする. ただし, 気に入らないならば (N-1) 回まで以下を行うことができる.
    • その結果を捨て, 振り直す.

このスコアが最大になるように行動した場合, スコアの期待値を求めよ.

制約

  • 1 \leq N \leq 100

解法

動的計画法で考える. {\rm DP}[i,a] で残り i 回振れ, 現在のダイスの出目が a である場合, 最良な選択をしたときの期待値とする.

まず, ベースケースとして

{\rm DP}[0,a]=a \quad (a=1,2,3,4,5,6)

である.

次に更新式について, 振り直すを選択した場合と確定させる場合それぞれについて場合分けする. ここで, 振り直すを選択した場合の期待値はその時点での出目に関係無いことに注意すると,

\displaystyle {\rm DP}[i,a]=\max \left(a, \dfrac{1}{6} \sum_{b=1}^6 {\rm DP}[i-1, b] \right)

である.

この動的計画法において, 最低でも1回はダイスを振らなくてはいけないことに注意すると, 求めるべき解答は

\dfrac{1}{6} \displaystyle \sum_{a=1}^6 {\rm DP}[N-1, a]

である.

なお, \displaystyle X_i=\dfrac{1}{6} \sum_{a=1}^6 {\rm DP}[i,a] とすると, X_0=\dfrac{7}{2} 及び, i \geq 1 のとき,

\begin{align} X_i &=\dfrac{1}{6} \sum_{a=1}^6 {\rm DP}[i, a] \\ &=\dfrac{1}{6} \sum_{a=1}^6 \max \left(a, \dfrac{1}{6} \sum_{b=1}^6 {\rm DP}[i-1, b] \right) \\ &=\dfrac{1}{6} \sum_{a=1}^6 \max \left(a, X_{i-1} \right) \\ \end{align}

となることも述べておく.