二分探索は配列上の値の探索だけじゃないよ、という話をするにあたって、ABC338C - Leftover Recipesの問題設定を参考にし以下の改題を作成したので、その解説をここに書きます。
問題設定の参考のみで改題前後で解法は異なりますが、改題後の問題も似たような設定がどこかで既出だと思いますが、ご了承ください。
問題
冷蔵庫にN種類の材料があり、順に材料1, 材料2, …, 材料N と呼びます。材料iはQiグラムあります。さて、あなたは麻婆豆腐を作ることにしました。麻婆豆腐１人前を作るのに、材料iがAiグラム必要です。料理は整数人分しか作れません(すなわち、1.5人前のようなを作り方は不可能です)。冷蔵庫にある材料のみをつかって、最大何人前の料理が作れますか？
制約
1 ≦N≦10^5, 1≦Qi≦10^18, 1 ≦Ai≦10^18,
入力値はすべて整数。
実行時間制限: 2sec
考察
まず、単純な全探索を考えます。例えば大きい方からx個作れるか？を試していくと、料理が1つも作れないようなケースで最大で10^18回のループが必要となり、これはO(NQ_i)で間に合いません。全探索ができないならば、この問題の特性を考え効率的に求める方法を考えなければいけません。全探索を「ちょっと効率的にする」工夫は可能ですが、それらを撃墜するテストケースを作成することもまた可能です。
以下、求め「作ることができる最大値」をkと置くこととします。この問題の上ではK以下の人数分の料理は必ず作ることができ、反対にKより大きい人数分の料理は作ることができません。例えば、最大で10人前の料理が作れるとすると、当然ですが9人前の料理を作ることができます。11人前の料理は作れません。
よって、「その人数分の料理を作成可能である」「その人数分の料理は作成不可能である」の2つの領域に分割し、その境界を探す二分探索を行うことによってこの問題を解くことができます。二分探索の初期値としては、
少なくとも0人分の料理が作成可能であることから下界は0
Qiがすべて10^18でAiがすべて1であるようなとき、10^18人前の料理が作成可能であるが、それ以上の料理は(制約の都合で)絶対に作成できないため、上界は10^18 + 1
を持てば良い。
上界をTとすれば計算量は判定毎にN個の要素をチェックする必要があるので、O(Nlog(T))で本問制約下で十分高速です。