7/23 解いた問題 - yamake's blog

$k$ 分でできるかどうかを $M$ についての線形時間で判定できるかつ、 $k$ 分でできるとき $k+1$ 分で必ずできる。

この二つの条件がそろっているので二分探索をしたくなります。

まず $a[i] \leq b[i]$ となる $a[i]$ は全て0になるまで操作をして大丈夫です。

残った山たちについて、 $b[i]$ が一番小さいもの以外も0になるまで操作して大丈夫です。

答えは $\sum{a[i]} - {min}_{a[i] \gt b[i]}{b[i]}$ となります。

決勝進出者を決める問題です。予選終了時速やかに決勝進出の連絡をするにあたって、まず決勝進出確定の条件について考えます。

残り $rem$ 人が決勝に進出できるとして、

$k$ 番目まで試合を行い、 $i \quad (i \leq k)$ 番目の試合で最高順位 $j$ 位を取った人がその試合で決勝進出を決められるかを考えます。

この人が決勝に進出できる条件は「残りの試合で $j$ 位より良い順位を取る人が $rem$ 人より少ないこと。」です。

残りの試合数は $n-k$ 試合で、 $j$ 位より良い順位は $j-1$ 個存在します。

従って $(n-k)*(j-1) \lt rem$ を満たすとき、 $i$ 番目の試合で $j$ 位を取った人は決勝進出を決めます。

試合を行った人たちのデータはheap_queueなどで{ 最高順位、その時のコンテストが何番目のコンテストか }をkeyにして保持するのが楽だと思います。

それぞれの試合においてheap_queueが空になるまでwhileを回しても十分間に合います。