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^+_3, c_1, b^-_2, b^-_3, c_2, c_3, b^-_4\)などの並べ方がある
  
• 「列にある2枚のカードの間」、「列の先頭」または「列の末尾」の\(B+C+2\)通りの場所に、選んでいない赤いカードを並べる。\({}_{B+C+2} \mathrm{H}_{A-1}\)通り
  

 

 したがって求める確率\(p(a^*, B^*)\)は、

 

\[\frac{(A-1)!k!(B-k)!C! {}_{C+1} \mathrm{H}_{B-k} {}_{B+C+2} \mathrm{H}_{A-1}}{(A+B+C)!} = \frac{k!(B+C-k)!}{(B+C+1)!}\]

 となります。これは選んだカードが何であるかには依存せず、青いカードを何枚選んだかに依存します。したがって以下では、\(p(a^*, B^*) = p(k)\)と書きます。

 青いカードを\(k\)枚選ぶような\(B^*\)の和を\(S(k)\)とすると、求める期待値\(E\)は

\[\begin{aligned} E &= \sum_{a^*} \sum_{B^*} p(a^*, B^*) a^* B^* \\ &= \sum_{i=1}^A \sum_{k=1}^B p(k) a_i S(k) \\ &= \sum_{i=1}^A a_i \sum_{k=1}^B p(k) S(k) \end{aligned}\]

となります。

\(S(k)\)は、次のDPで求まります。

\[dp(i, j) = \text{\(i\)番目までの青いカードを使って、\(j\)枚選ぶときの積の和}\]

\[dp(i, j) = \begin{cases} 1 &\text{if } j = 0 \\ dp(i - 1, j) + dp(i - 1, j - 1) * b_i &\text{if } j > 0 \end{cases}\]

 \(S(k) = dp(b - 1, k)\)です。

C#のソースコード

using System;

using System.Linq;

public class Program

{

    public static void Main()

    {

        string[] input = Next();

        var a = int.Parse(input[0]);

        var b = int.Parse(input[1]);

        var c = int.Parse(input[2]);

        input = Next();

        var cardAs = new int[a];

        for (var i = 0; i < a; i++) cardAs[i] = int.Parse(input[i]);

        input = Next();

        var cardBs = new int[b];

        for (var i = 0; i < b; i++) cardBs[i] = int.Parse(input[i]);

        var bStarSum = new double[1]; // S(k)

        bStarSum[0] = 1;

        for (var i = 1; i <= b; i++)

        {

            var tmp = new double[i + 1];

            var card = cardBs[i - 1];

            tmp[0] = 1;

            for (var j = 1; j < i; j++) tmp[j] = bStarSum[j] + bStarSum[j - 1] * card;

            tmp[i] = bStarSum[i - 1] * card;

            bStarSum = tmp;

        }

        var f = new double[a + b + c + 1]; // 階乗 factorial

        f[0] = 1;

        for (var i = 1; i <= a + b + c; i++) f[i] = f[i - 1] * i;

        var ans = 0.0;

        for (var i = 0; i <= b; i++) ans += bStarSum[i] * f[i] * f[b + c - i] / f[b + c + 1];

        ans *= cardAs.Sum();

        Console.WriteLine(ans);

    }

    static string[] Next(char separator = ' ') => Console.ReadLine().Split(separator);

}