水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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

  • 問題

C - Kill/Death

A, B 両チームのそれぞれのプレーヤー(それぞれ N, M 人)の Kill 数が分かっているとき、各プレーヤーの Death 数の通り数を求める問題。

 

  • 解法

両チームの中で同じ Kill 数のプレーヤーごとに区切り、何人グループかを調べる。A チームの Death 数は B チームの Kill 数と等しいので、「dp(i, j) := グループ i までで j だけ Death 数がある時の通り数」で DP をやろうと考える。同じグループ内では Death 数は順列ではなく組み合わせで処理するため、単純に重複組み合わせでは解けない。ここで詰まった。ネットで調べると、分割数というものがあることを知った。

drken1215.hatenablog.com

「f(i, j) := i を j 個の0以上の整数で表す時の通り数」と定義すると、次のような漸化式が立てられるらしい(実際に紙で実験した)。

f(i, j) = f(i, j - 1) + f(i - j, j)

あとは適切に端っこの自明な処理を書いて、DP にすればよい。

よって、DP の前処理で分割数を計算しておき、DP 中に各グループ内の通り数を O(1) で求められるようにすれば、全体として十分間に合う計算量になる。こんな複雑になるとは思わなかった。

 

  • 解答

Submission #2631062 - 第4回 ドワンゴからの挑戦状 予選

f:id:babcs2035:20180607220816p:plain

f:id:babcs2035:20180607220822p:plain