ABC 401-500/ABC448C - Except and Min - 競技プログラミング用 知識集積所

---

問題

ABC448C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

単純に毎回30万個のボールを全部チェックしていてはTLE。
よって、高速化を考える必要がある。

まず、全てのボールに書いてある数を、小さい順に並べたデータを用意する。（Kが最大5なので、小さい方から6個だけでも十分ではある）
そして、毎回、取り除くボールも書いてある数を小さい順に並べる。
2つのデータを比較し、袋の中に存在するが取り除くボール側に存在しない（また個数が少ない）最初のデータが答えとなる。
これなら最初のソートにO(NlogN)、クエリごとにO(KlogK)なので、十分間に合う。

解答例

解答例

注意点

別解

番号の方で探すこともできる。

袋のボールをソートするときに、vector<pair※<int,int>>で2番目に番号を持たせておく。
取り除くボールをset※に入れて、袋のボールの前から順にその番号がset※にあるかどうかを確認していってもよい。