ながめも

競技プログラミングについて

AtCoder Grand Contest B - Voting Judges

AGC AtCoder 二分探索

問題へのリンク

問題概要
制約
解説

問題概要

問題が $N$ 問あり、 $i$ 番目の問題のスコアは $A_i$ である。 $M$ 人が独立に $V$ 問選び、それらのスコアを $1$ ずつ上げる。 $M$ 人の選択後、スコアの降順に並べられ、最初の $P$ 問が採用される。採用される可能性のある問題は何問あるか？

制約

$1 \le N \le 10^{5}$
$1 \le M \le 10^{9}$
$1 \le V \le N-1$
$1 \le P \le N-1$
$1 \le A_i \le 10^{9}$

解説

以降0-indexedとする。問題を降順ソートする。上からP-1問目を含む同率順位までは、必ず選ばれる。この境界を $l$ とする。

今回、選ばれるかどうかの境界は、二分探索することができる。よって、問題 $x$ が選ばれるかどうかを $O(N)$ ほどかけて調べることを考えれば、問題を $O(N\log{N})$ で解くことができる。

$x \le l$ の場合

$x$ は必ず選ばれる。

$M$ 人が独立に $V$ 問選ぶ場合、一つの問題は最大で $M$ 回選ぶことが可能である。よって、 $x$ は、必ず $+M$ されると仮定してよい。

$A_x + M \lt A_l$ の場合

どう選んでも $A_x$ は上位 $P$ 問に入ることはできない。

$A_x + M \ge A_l$ の場合

選ばれる可能性があるかどうか判定したい。

$A_i \gt A_l$ なる $i$ は、 $+M$ してよい。 $x$ が上位 $P$ 問に入ることができるかどうかに関係しないからである。
$A_l \ge A_i \gt A_x$ なる $i$ は、 $A_x + M$ を超えないところまで、つまり、 $A_x + M - A_i$ だけ投票してよい。これ以上投票して $A_x + M$ を超えてしまうと、 $x$ が上位 $P$ 問に入ることができなくなる。
$A_x \ge A_i$ なる $i$ は、上位に影響しないので、 $+M$ してよい。

これらの $x$ が上位 $P$ 問になるために足していい数の合計が $M * V$ 以上あれば、 $x$ は上位 $P$ 問になることができると言える。 $M * V$ 未満だと、足せなくて溢れた票が $M$ 回足されていない他の問題に流れ、 $x$ が上位 $P$ 問に入れなくなる。

f:id:coonevo:20200406114429j:plain — sample 3