AtCoder ARC034 D
問題リンク https://atcoder.jp/contests/arc034/tasks/arc034_4 前提となる知識 重複組み合わせ \({}_n \mathrm{H}_r = \dfrac{(n + r - 1)!}{(n - 1)!r!}\) 解説 次のようにカードを引いた場合を考えます。 \[a_1, b_1, a_2, b_2, b_3, c\] このとき得点は\((a_1 b_1 + a_2) b_2 b_3 = a_1 b_1 b_2 b_3 + a_2 b_2 b_3\)です。\(a\)に\(b\)をいくつか掛け合わせて、それを足した形をしていることがわかります。 赤いカードから1枚選び\(a^*\)とし、青いカードから\(k\)枚を選んでその積を\(B^*\)とします。得点に\(a^* B^*\)が足し合わされる確率が分かれば、それに\(a^* B^*\)をかけたものについてすべての選び方に対して和をとることで答えが求まります。この確率は、得点に\(a^* B^*\)が足し合わされるような山札の並び方の総数をすべての山札の並び方の総数\((A+B+C)!\)で割ることで求めることができます。 条件を満たすような山札の並びは、次のようにしてすべて作ることができます。 選んでいない赤いカードをシャッフルして並べ替えておく。\((A-1)!\)通り 選んだ青いカードをシャッフルして並べ替えておく。\(k!\)通り 選んでいない青いカードをシャッフルして並べ替えておく。\((B-k)!\)通り 湯たんぽのカードをシャッフルして並べ替えておく。\(C!\)通り 「選んだ赤いカード1枚」、「選んだ青いカード\(k\)枚」、「湯たんぽのカード\(C\)枚」をこの順番で列に並べる。1通り 「選んだ赤いカードの直前」または「湯たんぽのカードの直後」の\(C+1\)通りの場所に選んでいない青いカードを並べる。\({}_{C+1} \mathrm{H}_{B-k}\)通り 例えば選んだ青いカードを\(b^+_1, b^+_2, b^+_3\)、選んでいない青いカードが\(b^-_1 \ldots b^-_4\)、湯たんぽのカードを\(c_1, c_2, c_3\)とすると、\(b^-_1, a^*, b^+_1, b^+_2, b^