ABC470 E - Concentration

考え方

実は、大きいカードを狙って引く方法は存在しない。
よって、各カードのペアを成立させられる確率は、すべて同一である。
したがって、ペアにできる組数の期待値を出せれば、それにカードの値の平均値をかければ答えとなる。

ペアにできる組数の期待値は、動的計画法で、値が小さいところから順に期待値を求めればよい。
dp[i][j][k] は、残りライフ $i$、残りペア数 $j$、片方見えているペア数 $k$、という状態での期待値とする。

dp[i][j][k] の値は、以下の $4$ つの寄与の総和で求まる。

$1$ つめ。
$1$ 枚目が既知のカードの相方だった場合。
これは、片方見えているペアが存在する場合のみ存在する。
そうなる確率は $\frac{k}{2j-k}$ で、それに $\mathrm{dp}[i][j-1][k-1]+1$ をかけた分が寄与となる。

$2$ つめ。
$1$ 枚目と $2$ 枚目が偶然ペアだった場合。
これは、どちらも見えていないペアが存在する場合のみ存在する。
そうなる確率は $\frac{2(j-k)}{(2j-k)(2j-k-1)}$ で、それに $\mathrm{dp}[i][j-1][k]+1$ をかけた分が寄与となる。

$3$ つめ。
$1$ 枚目は未知で、$2$ 枚目が既知のカードの相方だった場合。
これは、ライフが $2$ 以上かつ、どちらも見えていないペアが存在する場合のみ存在する。
そうなる確率は $\frac{2(j-k)k}{(2j-k)(2j-k-1)}$ で、それに $\mathrm{dp}[i-1][j-1][k]+1$ をかけた分が寄与となる。

$4$ つめ。
$1$ 枚目も $2$ 枚目も未知のカードだった場合。
これは、どちらも見えていないペアが $2$ 組以上存在する場合のみ存在する。
そうなる確率は $\frac{4(j-k)(j-k-1)}{(2j-k)(2j-k-1)}$ で、それに $\mathrm{dp}[i-1][j][k+2]$ をかけた分が寄与となる。

これら $4$ つの寄与を合計して dp[i][j][k] に入れることを繰り返していく。
全体を埋めたら、dp[L][N][0] の値がペア数の期待値。

最後に、忘れずにカードの値の平均値をかけたら答え。

計算量は $O(LN^2)$ である。

入力例1での動作

入力を受け取る。

n: 3
l: 2
a: {1, 2, 3}

dp[i][j][k] は、残りライフ $i$、残りペア数 $j$、片方見えているペア数 $k$ の状態を表す。
その値は、そこから獲得できるペア数の期待値である。

残りライフが $1$ の状態を小さい $j$ から求めると、次の値になる。

dp[1][1]: {1, 1}
dp[1][2]: {2/3, 4/3, 2}
dp[1][3]: {1/3, 4/5, 5/3, 3}

残りライフが $2$ の場合も同様に埋める。

dp[2][1]: {1, 1}
dp[2][2]: {2, 2, 2}

最後に必要な状態は dp[2][3][0] である。
この状態では、片方見えているペアがないので、考え方で挙げた $2$ つめと $4$ つめだけが発生する。

$1$ 枚目と $2$ 枚目が偶然ペアになる確率は $1/5$ である。
この場合は $1$ ペア獲得し、残りは $\mathrm{dp}[2][2][0]=2$ なので、期待値への寄与は $3/5$ となる。

$1$ 枚目も $2$ 枚目も未知で、異なるペアのカードを引く確率は $4/5$ である。
この場合はライフが $1$ 減り、片方見えているペアが $2$ 組になるので、遷移先は $\mathrm{dp}[1][3][2]=5/3$ である。
期待値への寄与は $(4/5)\times(5/3)=4/3$ となる。

したがって、$\mathrm{dp}[2][3][0]=3/5+4/3=29/15$ である。

カードの値の平均は $(1+2+3)/3=2$ である。
したがって、得点の期待値は $(29/15)\times2=58/15=3.866666\ldots$ となる。

注意点

特になし。

別解

特になし。