問題一覧 > 通常問題

No.1692 Expectations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 164
作問者 : eSeFeSeF / テスター : ir_1st_vilir_1st_vil 👑 ygussanyygussany
0 ProblemId : 5196 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-29 17:45:37

問題文

$N$ 人の人が参加するゲームがあります。彼らをそれぞれ人1、人2、...、人 $N$ と呼びます。

いま、$1$ 以上 $M$ 以下の各整数が 1 つずつあります。 このうち $N$ 個を選び、それを $N$ 人の人に $1$ つずつ渡します。

このゲームを観戦している SF くんは、それぞれの人がどの整数を持っているか当てたくなりました。 そこで、$N$ 個の予想を立てています。 $i$ 番目の予想は以下のようなものです。

  • 人 $i$ の持っている整数は $A_i$ である。

さて、SF くんの予想のうち、正しい予想の個数のありうる最大値と最小値を求めてください。 ここで、正しい予想とは、整数 $i$ であって、実際に人 $i$ が持っている整数が $A_i$ であるようなものをいいます。

入力

$N\ \ M$
$A_1\ \cdots \ A_N$
【制約】
  • $1\le N\le M\le 2\times 10^5$
  • $1\le A_i\le M$
  • 入力は全て整数

出力

SF くんの予想のうち正しいものの個数の最大値 $\max$ と最小値 $\min$ を、空白区切りで以下のように1行に出力せよ。
$\max\ \ \min$

サンプル

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

例えば、3人の持っている整数が (人1、人2、人3)$=(4,2,1)$ だった場合に予想は2つ正しくなります。 一方、全ての予想が正しいと仮定すると、$1$ が2つあることになり不適です。 したがって、正しい予想の個数の最大値は $2$ です。

持っている整数が $(2,3,5)$ だった場合などに全ての予想が外れている可能性があります。よって、最小値は $0$ です。

サンプル2
入力
8 8
7 1 2 5 8 3 4 6
出力
8 0

全ての予想が的中する場合も、全ての予想が外れる場合もあり得ます。

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