Codeforces Round #521 (Div. 3)E. Thematic Contests

問題概要

あるトピックについて出題される問題が $n$ 個ある. $i$ 番目の問題はトピック $a_i$ について述べている. これらの問題をまとめて, 数日にわたるコンテストを開く. コンテストに出題する問題の制約は以下である :

それぞれの日程について, その日一日に出題される問題のトピックはすべて同じであり, また同一のトピックについて二日以上出題することはできない.
$i$ 日目に $k$ 問出題されたとすると, $i+1$ 日目には $2k$ 問の問題を出題しなければならない( $1$ 日目は任意の個数の問題が出せる).

コンテストの日程を自由に決められるとき, 最大で合計何問の問題を出題することができるか？

制約

$1 \le n \le 2\times 10^5$
$1 \le a_i \le 10^9$

解法

出題しなければならない問題数はどんどん増えていくので, 最終日を最初に考えることにしましょう. まずは, 各トピックの種類数を std::map などでまとめ, 種類数の数列 $p_1, \cdots, p_k$ をつくります. なお, $p$ は昇順にソートされていることにします.

さて, 最終日に選ぶべきトピックはどれでしょうか？これは, $p_k$ を選ぶことが最適です. 最終日に $p_k$ 以外を選ぶことによって, 出題できる問題の総数が増えることはないためです.

同様の議論から最終日から一日前に出題するべきトピックは $p_{k-1}$ であることもわかります. これを繰り返すと, もし $T$ 日間のコンテストを開きたいならば, $p_{k-T+1}, p_{k-T+2}, \cdots, p_{k}$ のトピックからなるコンテストを開けばよいです. このとき, 出題できる問題数はもっとも問題がすくないトピックに合わせなければならないため, 初日に出題すべき問題数は $min(p_{k-T+1}, p_{k-T+2}/2, \cdots, p_{k}/2^{T-1})$ であり, これさえわかればあとは初等的な計算で全体の問題数がわかります.

肝心の $min$ の部分ですが, 動的に $min$ を管理するようにすれば良いです. 具体的には実装をみてください. 発想はこれが近いと思います.

実装

Submission #145930637 - Codeforces