TDPC J - ボール

考え方

ABCでいうと、E問題級。

bitDPによる期待値DP。
初期条件で的が歯抜けになっているが、位置が最大 $16$ しかないので、普通に bitDP しても間に合う。

各状態に対して、各位置を狙った場合の期待値の中の最小値を採用すればよい。
各位置を狙った場合の期待値は、自己遷移を含む期待値の式を立てれば求められる。

近隣 $3$ つのうち的がある位置の個数を $C$ とする。
それらの的に当たった後の期待値の合計を $S$ とする。
今の状態から、いずれかの的に当たるまではこの位置を狙い続ける場合の期待値を $E$ とする。

的に当たる確率は $C/3$。
的がない位置に飛んだ場合は状態が変わらず、その確率は $(3-C)/3$ である。
よって、次の式が成り立つ。

$$
E
=
1
+
\frac{S}{3}
+
\frac{3-C}{3}E
$$

これを整理すると、次の式になる。

$$
\frac{C}{3}E
=
1+\frac{S}{3}
$$

したがって、次の式になる。

$$
E
=
\frac{3+S}{C}
$$

あとは、前述のとおり、各位置を狙った場合の期待値の最小値を採用すればよい。
ただし、近隣 $3$ つに的がない場合は、$0$ 除算が発生する前にスキップ処理すること。

最後に、$x$ を見て初期状態に対応する情報を答えればよい。

考慮する位置の個数を $M$ とすると、計算量は $O(2^M M)$ である。

入力を受け取る。

n: 2
x: {0, 2}

考慮する位置は $0,1,2$ の $3$ つなので、m = 3 となる。
各位置に的が残っているかどうかを $3$ ビットで表す。

的がない状態では、残りの投球回数は $0$ なので dp[0] = 0 となる。

位置 $0$ の的だけが残っている状態を考える。
位置 $1$ を狙うと、位置 $0$ に飛ぶ確率は $1/3$ である。
位置 $1,2$ に飛んだ場合は状態が変化しない。

このとき、$C=1$、$S=0$ なので、$dp[1]=(3+0)/1=3$ となる。

同様に、位置 $2$ の的だけが残っている状態でも dp[4] = 3 となる。

初期状態では位置 $0,2$ に的があるので、ビット表現は 101 となる。
位置 $1$ を狙うと、どちらかの的に当たる確率は $2/3$ である。

このとき、$C=2$。
どちらかの的に当たった後の期待値は、それぞれ $3$ である。
よって、$S=3+3=6$ となる。

したがって、$dp[5]=(3+6)/2=4.5$ となり、答えは $4.5$。

特になし。

特になし。