Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 271 C問題 Manga

AtCoder ABC271 ABC C問題 300 pts

問題

提出解答

問題の概要

あなたはある連載されている漫画の単行本を $N$ 冊持っており, $i$ 番目の単行本は第 $A_i$ 巻である.

あなたはこの単行本たちを読み始める前に以下の行動を0回以上行うことができる.

持っている単行本を2冊売り, 好きな巻を1冊買う.

この行動終了後にこの単行本を第 $1$ 巻, 第 $2$ 巻,... と読み進めていくが, 次に読むべき巻が存在しない場合に読むのをやめる.

適切な単行本の売買によって, 最大で第何巻まで読めるか?

制約

$1 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

まず, 同じ巻の漫画を複数持っていても意味ないので, 重複分については売る専用の漫画にまわしても構わない. よって, 重複分については第 $(10^9+1)$ 巻, 第 $(10^9+2)$ 巻, ... とみなしても問題ない.

これによって, 持っている本の全ての巻は異なっているとしても構わない. そして, 並び替えて $A_1 \lt \dots \lt A_N$ であるとしてもよい.

そして, 漫画を読むことと漫画の売買を交互に行うことを可能にしても問題ない.

よって, 次のように行動することによって正解できる.

$i=1, j=N, X=0$ とする.
以下の行動をである限り行う.
- $A_i=X+1$ ならば, $i$ に1加算して ( $i$ 冊目を読んで) , $X$ に $1$ を加算する.
- のとき,
  - $i+1 \leq j$ ならば, $j$ から $2$ を減産して ( $(j-1), j$ 冊目を売って, 第 $(X+1)$ 巻を買う), $X$ に $1$ 加算する.
  - $i+1 \gt j$ ならば直ちに終了する.
$X$ を出力する.

このとき, $A$ を昇順に並べるソートがボトルネックになり, 計算量は $O(N \log N)$ 時間である.

なお, 答えの最大値が $N$ であることを考慮すると, 実は $O(N)$ 時間でも計算できる.