TopCoder SRM 673 (Div. 1) Easy. BearCavalry

配列 $a$ と $b$ が与えられ、 $a$ の要素と $b$ の要素をペアにしていく。 $a_i$ のペアを $b_i$ とするとき、 $a_0b_0 \gt a_ib_i$ になるような割り当ての方法は何通りあるか。

$a_0$ とペアになる要素を先に決めておく。ペアの積を $L$ としたとき、残りの配列でペアの積が $L$ 未満になるような割り当て方が何通りあるかを数え上げていこう。

$a_0$ とペアの数を $a$ と $b$ から除外し、 $a$ を降順に、 $b$ を昇順にソートする。

（注意：ここから添字が1-indexedに変わります）
$a_1$ との積が $L$ 未満であるような最大の $b$ の位置を $k$ とすると、 $a_1$ の割り当て方は $k$ 通り。

f:id:pekempey:20151119171839p:plain

$k$ を更新する。 $a_1\ge a_2$ なので $k$ は増える、あるいは変化しない。 $k$ 個のうち1個使われてしまっているので $a_2$ の割り当て方は $k-1$ 通り。

f:id:pekempey:20151119171843p:plain

$k$ を更新する。 $k$ 個のうち2個使われてしまっているので $a_3$ の割り当て方は $k-2$ 通り。

f:id:pekempey:20151119171847p:plain

これを繰り返していけば何通りかを求めることができる。

2回resubmitするとスコアが残酷なことになるという知見を得た。割りと早く解いていただけに微妙なミスに気づけなかったのは悲しい。