きままにものづくり

日々の気付いたことなんかを書いてます。

SRM635Div1Medium

問題

サイズNの数列placeとcutoffが与えられる。全ての要素でplace[i] \leq cutoff[i]となるために、place内で要素を入れ替える。入れ替えが必要な要素の最小数を求めよ。不可能な場合は-1を返す。

解法

二部マッチングで解こうとすると、 O(F V^2) \approx O(N^3)となり間に合わない。
貪欲法で解く。
すでにplace[i] \leq cutoff[i]の条件を満たしている集合goodと、満たしていない集合badを作成する。bad内でソートを行い条件を満たすかを値が小さい順に確認していく。満たさない要素を見つけたら、goodから要素を持ってきて満たすようにする。goodから持ってくる要素では、まず place_{good} \leq cutoff_{bad}を満たす必要がある。この条件を複数の要素が満たす場合は、その中で cutoff_{good}が最大の要素を選択する。
goodから要素を持ってこれなくなった場合は、条件を満たせないことになるので-1を返す。最後まで処理できた場合は、badの要素数が答えとなる。

計算量

O(N^2 log N)
ソート: O(N log N)

コード