ABC 401-500/ABC440D - Forbidden List 2 - 競技プログラミング用 知識集積所

---

問題

ABC440D

必要知識

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

• 二分探索※

考え方

ある値Zに対し、「X以上Z以下の全ての数の個数-X以上Z以下のうちAに含まれる数の個数」を考える。
Zを1ずつ増やしていくと、前者は必ず1増えて、後者は1増えるか変わらないか。
つまり、この引き算の結果は単調増加する。
ということは、これがY個以上になるZの最小値を探すには、答えを直接探す二分探索※でよい。

X以上Z以下の全ての数の個数は、Z-X+1個。
X以上Z以下のうちAに含まれる数の個数は、事前にAをソートした上で、A上で二分探索※をすればよい。

解答例

解答例

注意点

long long型が必要

答えは最大で約2*10^9になる。
ということは、二分探索※をこれより大きい値を初期値とする必要がある。
すると、中間の値を求めるときに約2*10^9同士の足し算が発生するため、ここでint型から溢れてしまう。

別解