けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

AtCoder AtCoder500点 unrated公式コン分割数数え上げ問題賢い漸化式漸化式 DP グラフ・盤面・数列の個数の数え上げデータ構造テク：前処理写像12相現実世界の題材を扱った問題アニメやゲームを元ネタとした問題トーナメントなど対戦表に関する問題

分割数のいい感じの問題！

問題へのリンク

問題概要

長さ $N$ の数列 killA, killB が与えられる。この 2 つの広義単調減少である。

次の条件を満たす長さ $M$ の数列 deathA, deathB の組の個数を 1000000007 で割ったあまりを求めよ。

killA の総和 = deathB の総和
killB の総和 = deathA の総和
killA[i] = killA[j] かつ $i \lt j$ ならば、deathA[i] $\ge$ deathA[i] である
killB[i] = killB[j] かつ $i \lt j$ ならば、deathB[i] $\ge$ deathB[i] である

制約

$1 \le N, M \le 1000$
killA, killB の要素の総和は $1000$ 以下

考えたこと

分割数が活躍する問題だ。

分割数は、「自然数 $n$ を $k$ 個の 0 以上の整数の和で表す方法の数」のことであり、 $P(n, k)$ と表すことにする。。ただし、和として表すときの順序は問わない。

たとえば、 $n = 5, k = 3$ のときは

$0 + 0 + 5 = 5$
$0 + 1 + 4 = 5$
$0 + 2 + 3 = 5$
$1 + 1 + 3 = 5$
$1 + 2 + 2 = 5$

というように 5 通りの方法があるので、 $P(5, 3) = 5$ である。

分割数は、次の漸化式で求められる。

$\displaystyle P(n, k) = P(n, k-1) + P(n-k, k)$

この漸化式の導出方法としては、自然数 $n$ を $k$ 個の 0 以上の整数の和で表す方法のうち、 $0$ を含むものと含まないものに場合分けして考える。

$0$ を含むとき、その $0$ を除去しても方法の数は変化しないので、 $n$ を $k-1$ 個の整数の和として表す方法の個数に等しい。よって、 $P(n, k-1)$ 通り。
$0$ を含まないとき、和が $n$ となる $k$ 個の各整数から $1$ ずつ引くことで、「 $n-k$ を $k-1$ 個の $0$ 以上の整数の和として表す方法」に帰着される。よって、 $O(n-k, k)$ 通り。

これらをまとめて、上記の漸化式が得られる。

今回の問題

今回の問題では、killA, killB の値が等しい区間の扱いが若干面倒である。killA, killB が等しい区間はまとめて処理したい。

そこで、数列 $A$ を次のように、整数値のペアの列とする。

$A_{i}$ = (killA において $i$ 番目に大きい数 $a_{i}$ , killA におけるその数の個数 $n_{i}$ )

このとき、deathA の個数を求めるのは次の DP でできる。なお、deathB の方も同様である。

dp[i][j] ← deathA の先頭から $n_{0} + \dots + n_{i-1}$ 個までについて、総和が $j$ となるようなものの個数

DP の遷移は次のように書ける。分割数が登場する。

dp[i+1][j+k] += $P(k, n_{i}) \times$ dp[i][j]

計算量は $S$ = (killA や killB の総和としてあり得る最大値) として、

分割数を前処理する： $O(NS)$
DP する： $O(NS^{2})$

となる。

コード

提出したコード