Codeforces Round #521 (Div. 3)D. Cutting Out

問題概要

長さ $n$ の数列 $s$ と非負整数 $k$ が与えられる. $a$ に対して, 長さ $k$ の数列 $b$ の Cutting Out を以下のように定める :

$b$ の各要素を一回ずつ $a$ から削除する. もし削除できない要素がひとつでもある場合, Cutting Out はできない.

$b$ の要素は重複することができるため, $b$ の要素をすべて $a$ が含んでいても Cutting Out できない場合があることに注意せよ. 例えば, $a = \{1, 2, 2, 3\}, b = \{1, 1, 2\}$ のとき, $b$ の要素を $a$ はすべて含んでいるが, $1$ を $2$ 回削除することはできないので Cutting Out ができない.

このとき, 適切に $b$ を定めることにより連続してできる Cutting Out の回数を最大化したい. どのように $b$ を定めればよいか？

問題へのリンク

制約

$1 \le k \le n \le 2\times 10^5$
$1 \le s_i \le 2\times 10^5$

解法

貪欲にやってうまくいかなさそうな最大化の問題は, 二分探索を考えるとうまくいくことが多々あります. この問題でも二分探索を考えてみましょう.

$T$ 回 Cutting Out することは可能か？という判定問題を考えます. $a$ がある要素を $k$ 個含んでいるとき, $T$ 回 Cutting Out するにはこの要素は $b$ には $floor(T/k)$ 個までしか含むことができません. そこで, $a$ の全ての要素について, $b$ に含むことができる要素の個数を総和して, これが $k$ 以上ならば $T$ 回の Cutting Out が達成できて, 逆に $k$ 未満ならばどうやっても $T$ 回はかないません.

この判定問題は $O(n)$ で解くことができるので, 全体として $O(n\mathrm{log}n)$ で問題を解くことができました.

実装

std::map を用いているので計算量は $O(n(\mathrm{log}n)^2)$ となっています.

Submission #145862633 - Codeforces