ABC470 E - Concentration

考え方

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

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

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

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

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

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

$4$ つめ。
$1$ 枚目も $2$ 枚目も未知のカードだった場合。
これは、どちらも見えていないペアが $2$ 組以上存在する場合のみ存在する。
そうなる確率は $\frac{4(j-k)(j-k-1)}{(2j-k)(2j-k-1)}$ で、それに 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] は、考え方で説明した通りの期待値とする。
初期値はすべて $0$ とし、i, j, k の順に小さい方から埋めていく。

i=1 のとき、各状態は次のようになる。

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

続いて i=2 の状態を埋める。

dp[2][1]: {1, 1}
dp[2][2]: {2, 2, 2}
dp[2][3]: {29/15, 43/15, 3, 3}

よって、獲得できるペア数の期待値は dp[2][3][0] $=\frac{29}{15}$ である。

カードに書かれた値の合計は、$1+2+3=6$ なので、平均は $6\div 3=2$。
したがって、答えは $\frac{29}{15}\times 2=\frac{58}{15}=3.866666\dots$

注意点

特になし。

別解

特になし。