Kazun の競プロ記録

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

AtCoder Beginner Contest 290 C問題 Max MEX

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ  N の整数列 [tex A:=(A_1, \dots, A_N)] の長さ  K の部分列  B における   \operatorname{MEX}(B) の最大値を求めよ.

ただし, 数列   X に対する   \operatorname{MEX}(X) とは以下を満たす唯一の非負整数  M として定義される.

  •  M 未満の全ての非負整数  i X に含まれる.
  •  M X に含まれない.

制約

  •  1 \leq K \leq N \leq 3 \times 10^5
  •  0 \leq A_i \leq 10^9

解法

次のようなアルゴリズムで正解できる.

  •  x=0,1, \dots, K-1 の順に対して, 以下を実行する.
    •  A の中に  x が存在しないならば,  x を返し, 強制終了する.
  •  K を返す.