pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 673 (Div. 1) Easy. BearCavalry

問題概要

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

解法

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

a_0とペアの数をabから除外し、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

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

TopCoder SRM 673 (Div. 1) Easy. BearCavalry

感想

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