AtCoder 第4回 ドワンゴからの挑戦状 予選 : C - Kill/Death
-
問題
A, B 両チームのそれぞれのプレーヤー（それぞれ N, M 人）の Kill 数が分かっているとき、各プレーヤーの Death 数の通り数を求める問題。
-
解法
両チームの中で同じ Kill 数のプレーヤーごとに区切り、何人グループかを調べる。A チームの Death 数は B チームの Kill 数と等しいので、「dp(i, j) := グループ i までで j だけ Death 数がある時の通り数」で DP をやろうと考える。同じグループ内では Death 数は順列ではなく組み合わせで処理するため、単純に重複組み合わせでは解けない。ここで詰まった。ネットで調べると、分割数というものがあることを知った。
「f(i, j) := i を j 個の０以上の整数で表す時の通り数」と定義すると、次のような漸化式が立てられるらしい（実際に紙で実験した）。
f(i, j) = f(i, j - 1) + f(i - j, j)
あとは適切に端っこの自明な処理を書いて、DP にすればよい。
よって、DP の前処理で分割数を計算しておき、DP 中に各グループ内の通り数を O(1) で求められるようにすれば、全体として十分間に合う計算量になる。こんな複雑になるとは思わなかった。
-
解答
Submission #2631062 - 第4回 ドワンゴからの挑戦状 予選
