ABC 228 D - Linear Probing
問題
自分のコード
感想
なんでやねんと思ったけどC++のsetの構造とイテレーターの理解をしなければ難しかった。大事なアルゴリズムの部分は問題なし。
考え方
考え方はは単純なクエリ処理で、一回も1のクエリで処理されていないならそのまま、そうでないならそこから一番近い一度も処理されていない場所に代入する。ただし、添え字は最後まで行ったら最初に戻る(mod N)で管理する。という内容。基準からある条件を満たす一番近い大きい(小さい)数を探すときは二分探索が高速。なのでまだ一度も処理されていない添え字をsetで管理してそのなかで二分探索をしていく。
使った知識
ここからが本題でsetの二分探索をしたのは今回が初だからしかたないが、setの二分探索はlower_bound(all(s), x)ではなく、s.lower_bound(x)と書く。こうしないと前者では線形探索しているのと同じになってしまう。説明は以下の通り。
まずそもそもvectorなどの配列は箱のようなもので管理しているのに対し、setは平衡二分探索木で管理している。
また、イテレータには種類があるというのは知っていたと思うが、lower_boundの場合はn個先をランダムに参照するというイテレータを採用していて、これとsetはデータ構造の観点から非常に時間がかかっしまう。のでset独自のlower_boundをもっているためs.lower_bound(x)と書く。詳しくは下参照。
簡単な方
詳しく書いてあるほう