ABC 401-500/ABC405B - Not All - 競技プログラミング用 知識集積所

---

問題

ABC405B

必要知識

A問題レベルのものは省略

• set（未作成）

考え方

種類数を扱うならset（未作成）の出番。
空のset（未作成）を用意し、与えられたvector（未作成）の前から順にemplace()していく。
そして、1つemplace()するたびにset（未作成）の大きさを.size()で確認する。
それが初めてm個になったとき最後に追加した数が、後ろから消すべき最後の1つとなる。

入力例1の場合、

iの値	vectorの中身					setの中身	size()	解説
i=0	3	2	3	1	2	{3}	1
i=1	3	2	3	1	2	{2,3}	2
i=2	3	2	3	1	2	{2,3}	2
i=3	3	2	3	1	2	{1,2,3}	3	setが3個になったので、後ろからここまで削除したい

となる。
よって、setが初めて3個になったタイミングで5-3つまりn-iの値を答え、break;でループを抜ければよい。

解答例

解答例

注意点

vector（未作成）の添え字は0スタートなので注意。

iが3のときに条件を満たした場合、4番目の数を見ているので、残したい個数は3個である。

そもそも全部そろってない場合の挙動を確認すること。

入力例2のようなケースもある。
今回の実装では最後までsizeがmにならないが、その場合に何が出力されるかよく考えなければならない。
何も出力されない場合や異なるものが出力される場合は、特別対応をしなければならない。

別解