問題一覧 > 通常問題

No.2126 MEX Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : 遭難者遭難者 / テスター : 👑 p-adicp-adic 👑 potato167potato167
4 ProblemId : 8761 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-31 10:38:25

問題文

長さ $N$ の非負整数列 $A=(A_1,\ldots,A_N)$ が与えられます。

Sente君とGote君はこの非負整数列を使ってゲームをします。

Sente君の先手で $2$ 人は交互に以下の行動をそれぞれ $1$ 回ずつ、 $2$ 人合わせて $10^{5000}$ 回行います :

  • $1\le k\le N$ を満たす整数 $k$ と $0\le x\le 10^5$ を満たす整数 $x$ を選び、 $A_k$ を $x$ に変更する。

    • Sente君は $2$ 人の全ての操作が終わった後の $A$ の mex が大きくなるように、Gote君は小さくなるように行動します。

    両者がそれぞれ自身の目標が満たされるようにするために最適な戦略をとる場合の $2$ 人の操作が全て終わった後の $A$ の mex の値を求めてください。


    ただし、 $A$ の mex とは以下のように定義されます :

  • 全ての $1\le i\le N$ に対し $A_i\neq X$ を満たすような最小の非負整数 $X$ 。

    • 制約

  • $1\le N\le 10^5$
  • $0\le A_i\le 10^5$
  • 入力は全て整数である。

    • 入力

    $N$
$A_1$ $A_2$ $\ldots$ $A_N$

    出力

    操作全てが終わった後の $A$ の mex の値を出力してください。

    サンプル

    サンプル1
    入力
    3
0 1 0
    出力
    1

    Sente君は $A$ の $0$ でない要素を $0$ にする (ただしそのような要素がない場合は $A_1$ を $0$ にする) 操作を繰り返すことで最終的な $A$ の mex を $1$ にすることができます。
    逆にSente君は $A$ の mex を $2$ 以上にすることはできないので、 $1$ を出力してください。

    サンプル2
    入力
    1
2022
    出力
    0

    Sente君がどのように操作しても例えばGote君が $A_1$ を $2040$ に変更することで最終的な $A$ の mex を $0$ にすることができます。

    サンプル3
    入力
    9
0 0 0 1 1 0 0 1 1
    出力
    2

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。