ABC 401-500/ABC417B - Search and Delete - 競技プログラミング用 知識集積所

---

問題

ABC417B

必要知識

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

• 特になし

考え方

bの要素それぞれ、aの要素と順に比較していき、同じ値があったらそのうち1つを取り除く。
問題文に書いてある通りに素直にやって、最初に見つけた1つを消すようにすればいい。

問題は、真ん中あたりから取り除くというのが、vectorでは難しい点。
そこで、取り除く代わりに-1に変更をしておき、出力時に-1をスキップすることで解決する。

解答例

解答例

注意点

別解

list※を使う

途中をいきなり削除と言えばlist※。
これなら、-1に書き換えるなんて露骨な回避策を書かなくてもよくなる。
ただし、forループはイテレータ※で回す必要がある上に、ランダムアクセスができないので、書き方がわりと面倒。
解答例

Bをソートして併走型の線形探索※をする

Bの順番は結果に影響を与えないので、Bをソートしてから併走型の線形探索※をすると高速化できる。
番兵法※も活用するとなおよし。
NやMが10^6くらいあっても大丈夫だが、そもそもB問題で高速化する意味自体は全くない。
解答例