ACL Beginner Contest F - Heights and Pairs

解法

まずは入力を各身長ごとの人数として集計します。 $a_{i}$ を身長が $i$ である人の人数とします。 $\sum_{i} a_{i} = 2N$ であり、 $0$ 人であるような身長を無視すれば身長の種類数は $2N$ 以下です。

条件を満たす組み方をDPなどで直接数えようとすると、 $O(N^{2})$ から落ちず厳しいです。

包除原理を適用します。同じ身長で組んでいるペアを「違反ペア」と呼ぶことにして、違反ペアを $0$ 個以上集めた集合を $s$ とします。「 $s$ に含まれるペアは必ず組んであって、その他のペアは自由に組まれているような組み方の数」を $C(s)$ とすると、答えは包除原理から

$\displaystyle \sum_{s} (-1)^{|s|}C(s)$

と計算できます。集合 $s$ の取り方は膨大にあるので $s$ のサイズごとに集計することにします。

まずはそれぞれの身長ごとに独立に、違反ペアをいくつか組む組み方を数えます。以下の値を計算します。

$c\lbrack i\rbrack\lbrack k\rbrack =$ 身長が $i$ の人の中で、違反ペアをちょうど $k$ 組だけ組むような組み方。（それ以外の人の組み方はまだ決めない）

これはまず、違反ペアに参加する人を選ぶのが $_{a_{i}}C_{2k}$ 通り。その中で違反ペアを組む組み方は、

まず $1$ 人適当に誰かを選び、その人の相方を残りの $2k-1$ 人の中から選ぶ。
また $1$ 人適当に誰かを選び、その人の相方を残りの $2k-3$ 人の中から選ぶ。
…

と考えると、二重階乗を用いて $(2k-1)!!$ 通りと計算できます。この $k$ は $0$ から $\lfloor\frac{a_{i}}{2}\rfloor$ まで取り得ます。

各身長ごとに求めた数列 $c\lbrack i\rbrack$ を全てマージします。身長 $1$ の人の違反ペアが $b_{1}$ 組、身長 $2$ の人の違反ペアが $b_{2}$ 組…という組み方を合わせると、合計違反ペアが $b_{1} + b_{2} + \cdots$ 組であるような組み方が $c\lbrack 1\rbrack\lbrack b_{1}\rbrack\times c\lbrack 2\rbrack\lbrack b_{2}\rbrack\times\cdots$ 通り得られます。これを全ての $(b_{1}, b_{2}, ...)$ について計算するので、これは数列をFFT（NTT）でマージすることに相当します。

これを最後までマージすると、以下の値を示す数列が得られます。

$c_{all}\lbrack k\rbrack =$ 全ての人の中で、違反ペアをちょうど $k$ 組だけ組むような組み方。（それ以外の人の組み方はまだ決めない）

これに残りのペアの組み方 $(2(N-k)-1)!!$ を掛けると、「 $|s| = k$ であるような $s$ についての $C(s)$ の和」が得られます。これを包除原理の式に従い合計すると答えになります。

あとはNTTのマージにかかる計算量を落とす必要があります。各身長に対する $c\lbrack i\rbrack$ の長さは $\lfloor\frac{a_{i}}{2}\rfloor + 1$ であり、 $\sum_{i} a_{i} = 2N$ なので、全ての数列の長さの和は $2N$ 以下です。

何も考えずにマージすると、長い数列に短い数列を何回もマージするような場合に最悪で $O(N^{2}\log N)$ の計算量が掛かってしまいます。

マージの順番を工夫して、以下の二分木のようにマージをするとどうでしょうか。

f:id:betrue12:20200927042025p:plain

二分木の1段分のマージでは、長さの和が $2N$ 以下である数列たちが1度ずつNTTでマージされるので、合計で計算量 $O(N\log N)$ になります。そして二分木のようにマージすると $O(\log N)$ 段で全てマージし終わるので、全体計算量 $O(N (\log N)^{2})$ でマージできます。