Codeforces Round #540 (Div. 3)D2. Coffee and Coursework (Hard Version)

問題概要

n 杯のコーヒーがあり, i 番目のコーヒーは a_i だけのカフェインを含有している. このコーヒーを飲むことで, m 個ののタスクをこなしたい.

ある一日で a_{i_1}, a_{i_2}, \cdots,  a_{i_k} 番目のコーヒーを飲んだとすると, a_{i_1} + max(0, a_{i_2} - 1) + \cdots + max(0, a_{i_k} - k + 1) だけのタスクをこなすことができる.

このとき, 最小で何日ですべてのタスクをこなすことができるか？ただし各コーヒーは一回しか飲むことができない.

問題へのリンク

制約

  • 1 \le n \le 2\times 10^5
  • 1 \le m \le 10^9
  • 1 \le a_i \le 10^9

解説

こういう数列をうまいこと消費して最小値を求めるような問題は, 二分探索で答えを求めることが多いです. 今回も二分探索で答えを求めていきます.

T 日ですべてのタスクをこなせるか？を考えましょう. この Yes/No 判定が線形でできれば二分探索は O(N\mathrm{log}N) で機能します.

まず考えることとして, T 日間それぞれでのむコーヒーの数はなるべく均等である方がよいです. なぜなら, 例えば 5 つのコーヒーを 3 日で飲むとき, 1, 1, 3 と飲むと得られるカフェインは 3 減りますが, 1, 2, 2 と飲めば 2 減るだけで済みます. もちろん max を取る関係上均等に割り振らなくても変わらない場合はありますが, 均等に割り振らないことでメリットを得るような選び方は存在しません.

では均等に割り振ることにするならば, どのように飲むのが最適でしょうか？これは, 各日程の最初に飲むコーヒーを大きい順に割り当て, 2 杯目に飲むコーヒーを残りから大きい順に割りあて, ... といった風に割り当てるのが最適です. これは, 減るカフェインの上限がそのコーヒーの含有するカフェイン量であることから, 後の方に少ないカフェインのコーヒーを飲めば正味のカフェイン減少量を少なくすることができるためです.

こうして T を決めた時の判定問題が線形で解けることが分かったので, 問題全体は O(N\mathrm{log}N) で解けることがわかりました.

実装

Submission #145629735 - Codeforces