No.3024 全単射的
タグ : / 解いたユーザー数 50
作問者 : 👑
注意
この問題の実行時間制限は5000[ms]です。
問題文
最初に正整数 $N$ と $2$ 以上の整数 $M$ が与えられます。
とあるお祭りに射的大好きbotという $N$ 体のbotが参加しました。それらは $N$ 以下の各正整数 $i$ で番号付けられ射的大好きbot $i$ と呼ばれています。
お祭りと言えば射的です。$N$ 体の射的大好きbotたちは一斉に同一の射的屋に行きました。その射的屋には $M$ 個の景品が台上に左右 $1$ 列に並んでおり、$M$ 以下の各正整数 $j$ に対し左から $j$ 番目の景品は景品 $j$ と呼ばれています。台上に並んでいる景品に向かって射的の弾を撃って当てれば、その景品は床に撃ち落とされます。
ここで $N$ 以下の任意の正整数 $i$ に対し、射的大好きbot $i$ は景品 $X_i$ か景品 $Y_i$ の $2$ つのうちいずれか $1$ つ($X_i$ と $Y_i$ は $M$ 以下の相異なる正整数)に向かって射的の弾を撃とうとしていますが、$1$ 発分しか射的の弾を持っておりません。
$N$ 体の射的大好きbotが撃ち落とせる景品の総数の最大値を求めてください。
入力
入力は以下の形式で標準入力から $1 + N$ 行で与えられます:
- $1$ 行目に $N, M$ が半角空白区切りで与えられます。
- $N$ 以下の各正整数 $i$ に対し、$1+i$ 行目に $X_i,Y_i$ が半角空白区切りで与えられます。
$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$
制約
入力は以下の制約を満たします:
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $M$ は $2 \leq M \leq 10^{18}$ を満たす整数である。
- $N$ 以下の任意の正整数 $i$ に対し、$X_i, Y_i$ は $1 \leq X_i < Y_i \leq M$ を満たす整数である。
出力
$N$ 体の射的大好きbotが撃ち落とせる景品の総数の最大値を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 1 2
出力
1
射的大好きbotは $1$ 体しかいません。射的大好きbot $1$ は景品 $1$ か景品 $2$ に向かって撃とうとしていますが、射的の弾を $1$ 発分しか持っていないので撃ち落とせるのはいずれか $1$ 個のみです。
集合論を知っている人向けに言うと、上記の状況ではどの射的大好きbotがどの景品を落としたかの対応を見ることで、$N = 1$ 以下の非負整数全体の集合から $M = 2$ 以下の非負整数全体の集合への全射でない単射が得られます。
サンプル2
入力
2 3 1 2 1 2
出力
2
射的大好きbotが $2$ 体います。どちらも景品 $1$ か景品 $2$ に向かって撃とうとしており、景品 $3$ に向かって撃つことはありません。それぞれが別々の景品に向かって撃って当てることで合計 $2$ 個の景品を撃ち落とすことができます。
集合論を知っている人向けに言うと、上記の状況ではどの射的大好きbotがどの景品に向かって撃ったかの対応を見ることで、$N = 2$ 以下の非負整数全体の集合から $M = 3$ 以下の非負整数全体の集合への全射でない単射が得られます。
サンプル3
入力
3 2 1 2 1 2 1 2
出力
2
射的大好きbotが $3$ 体います。いずれも景品 $1$ か景品 $2$ に向かって撃とうとしています。例えばいずれか $2$ 体が同じ景品に向かって撃ってどちらかの弾が当たり、残りの $1$ 体がもう片方の景品に向かって撃って当たれば、合計 $2$ 個の景品を撃ち落とすことができます。
集合論を知っている人向けに言うと、上記の状況ではどの射的大好きbotがどの景品に向かって撃ったかの対応を見ることで、$N = 3$ 以下の非負整数全体の集合から $M = 2$ 以下の非負整数全体の集合への単射でない全射が得られます。
サンプル4
入力
3 3 1 3 1 3 1 3
出力
2
射的大好きbotが $3$ 体います。いずれも景品 $1$ か景品 $3$ に向かって撃とうとしており、景品 $2$ に向かって撃つことはありません。例えばいずれか $2$ 体が同じ景品に向かって撃ってどちらかの弾が当たり、残りの $1$ 体がもう片方の景品に向かって撃って当たれば、合計 $2$ 個の景品を撃ち落とすことができます。
集合論を知っている人向けに言うと、上記の状況ではどの射的大好きbotがどの景品に向かって撃ったかの対応を見ることで、$N = 3$ 以下の非負整数全体の集合から $M = 3$ 以下の非負整数全体の集合への全射でも単射でもない写像が得られます。
サンプル5
入力
3 3 1 2 2 3 1 3
出力
3
射的大好きbotが $3$ 体います。射的大好きbot $1$ は景品 $1$ か景品 $2$ に向かって撃とうとしており、射的大好きbot $2$ は景品 $2$ か景品 $3$ に向かって撃とうとしており、射的大好きbot $3$ は景品 $1$ か景品 $3$ に向かって撃とうとしています。例えば $N = M = 3$ 以下の任意の正整数 $i$ に対し射的大好きbot $i$ が景品 $i$ に向かって撃って当てることで、合計 $3$ 個の景品を撃ち落とすことができます。
集合論を知っている人向けに言うと、上記の状況ではどの射的大好きbotがどの景品に向かって撃ったかの対応を見ることで、$N = 3$ 以下の非負整数全体の集合から $M = 3$ 以下の非負整数全体の集合への全単射が得られます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。