No.794 チーム戦 - D言語で競プロ

概要

N 人(偶数)の人がいて、i 番目の人は整数 A_i を持っている。これらの人々を使ってペアを N / 2 組作りたい。ただし、各ペア(i, j)について A_i + A_j <= K が成り立っていないといけない。

そのようなペアの分け方は全部で何通りあるか？

制約

$2 \le N \le 2 \cdot 10^5$ , $N$ は偶数
$1 \le K \le 2 \cdot 10^9$
$1\le A_i \le 10^9$

考察

まず人の順番は無視していいので、 $A_i$ は昇順にソートしておくことにする。すなわち $A_1 \le A_2 \le \dots \le A_N$ が成り立っているものとする。

「２人の和がK以下」という制約が無ければ簡単で、答えは

$\binom{N}{2} \cdot \binom{N-2}{2} \dots \binom{2}{2} / (N / 2)!$

となる。最後に $(N / 2)!$ で割らなければいけないことに注意する。なぜなら、例えば[1,2,3,4,5,6]とあるとき、({1,2}, {3,4}, {5,6}), ({1,2}, {5,6}, {3,4}), ({3,4}, {1,2}, {5,6})...のように同じ分け方でも順序が違うものを重複して数えてしまうからだ。

上の考察は無駄ではなくてKが十分大きいときはこの答えがそのまま使える。より厳密に言うと、 $A_{N-1} + A_{N} \le K$ であるとき上の答えに帰着される。

こういうのは相方の候補数が少ないもの、つまり $A_i$ が大きい順に考えてその候補数を掛け算していけばよさそうな感じがする。 $A_i$ の相方の集合より $A_{i-1}$ の相方の集合のほうが大きいので、 $A_i$ がどれを相方にしても、 $A_{i-1}$ の相方候補は1つ減るだけだから。（これを逆順にやってしまうとややこしくなってしまう……ということをABC114-Dで学んだ）

そうやりたいんだけど、問題は $A_i$ が $A_{i-1}$ をペアにした場合とかを考えると、次に $A_{i-1}$ を考えるのではなく $A_{i-2}$ を考えなければいけない、みたいになってかなりややこしくなってしまう。どうすればいいんだろう……？

よく考えると $A_i$ が $A_{i-1}$ とペアになれるっていうことは、 $A_i + A_{i-1} \le K$ が成り立っているということで、これは上の「制約が無いパターン」に帰着されていることが分かる。すなわち、 $A_i + A_{i-1} \le K$ が成り立っているときは、前のi人は自由にペアを組めるのだ。

なので、 $A_i + A_{i - 1} \le K$ がどこまで成り立つか？でグループ分けすると考えやすくなるのではないか、という考えが浮かぶ。すなわち $A_i + A_{i - 1} \le K$ を満たす最大の $i$ をmとして、前半組m人、後半組N - m人と分けてみよう。すると前半組のm人はどの２人を選んでもペアに出来るし、後半組のN-m人はどの２人を選んでも絶対にペアに出来ないことが分かる。ということは後半組は相方を前半組から取ってこなければいけない、ということも分かる。