第22回日本情報オリンピック　一次予選(第2回)

2022年10月18日
情報オリンピック日本委員会

解説

for 文など繰り返し処理を用いて，ラウンド 1 からラウンド N までの点数の推移を順々にシミュレーションすればよい．

二重ループを用いて実装すると計算量は O(NM) であり，この問題の制約のもと，満点を得ることができる．

しかしながら，この問題は計算量 O((N+M) log M) で解くことも可能である．数列 B をはじめに sort しておくことで，数列 B に値が含まれているか否か調べる際に二分探索を行うことができる．毎回の二分探索にかかる計算量は O(log M) であり，シミュレーション全てを計算量 O(N log M) で行うことができる．はじめの sort に計算量 O(M log M) かかるため，合計で計算量 O((N+M) log M) で解くことができる．

C++ の std::set や，python の set 型を用いても高速にこの問題を解くことが可能である．