第4回 ドワンゴからの挑戦状 予選 C - Kill/Death

• 問題
• AC

チームA、Bについての場合の数を別々に計算してかけ合わせればよい。以下、$killA_1 + ... + killA_N = K_A$, $killB_1 + ... + killB_M = K_B$とし、分割数（自然数$n$の$k$個以下の分割）を$p(n, k)$とする。

チームAでキル数が同じメンバーを先頭から順にグループ化し、$i$番目のグループの人数を$a_i$とする。また、グループの総数を$G_A$とする。

グループ$a_1, ..., a_x$に総デス数$y$を割り振る場合の数を$f_A(x, y)$とすると、
$\begin{aligned} f_A(x, y) = f(x-1, y)p(0, a_{x}) + f(x-1, y-1)p(1, a_{x}) + \\ ... + f(x-1, 0)p(y, a_{x}) \qquad (x \neq 0) \end{aligned}$

$f_A(0, y) = \begin{cases} 0 \qquad (y \neq 0) \\ 1 \qquad (y = 0) \end{cases}$

である。このとき、チームAにデス数を割り振る場合の数は$f_A(G_A, K_B)$であり、同様に$f_B$を定めると、答えは$f_A(G_A, K_B)f_B(G_B, K_A)$である。

計算量について。$K=\max(K_A, K_B)$とすると、単純計算では高々$(N+M)K^2\le2 \times 10^8$回のループで済むし、漸化式を観察するとその半分にはなっているので間に合うはず……と考えて提出したのだが、実際の実行時間は250ms程度だったので面食らった。改めて考えてみると、グループの総数には$0 + 1+2+ ... + (G_A-1) \le K_A$という制約がつくので、$G_A = {\mathcal O}(\sqrt{K_A})$である。つまり、計算量は${\mathcal O}(G_AK_B^2 + G_BK_A^2) \subseteq {\mathcal O}(K^{2.5})$になる。実際のループ回数も$5 \times 10^7$以下におさまるはずで、それならひとまず納得がいく。

あと、コードテストで

45 45
54 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
54 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

を試したところ、500ms以上はかかりそうだったので、テストケースに最悪ケースはなかったのだろう。

分割数のコーナーケース

$p(n, k)$の境界の値は次のように定めるとつじつまが合うっぽいのでメモ。

$P(0, k) = 1$
$P(n, 0) = 0 \qquad (n \neq 0)$
$P(n, k) = P(n, n) \qquad (k > n)$

別解

もっと速いDPが可能らしい？
https://kimiyuki.net/writeup/algo/atcoder/dwacon2018-prelims-c/