AtCoderで最大値や最小値を求める問題に出会ったとき、二分探索を使えるかは、候補を並べて作ったyes/no判定が一度だけ切り替わるかで決まります。判定が単調なら、すべての候補を試さずに境界を探せます。
この判断には、判定関数の向き、lowとhighの意味、返す端点を先に固定する必要があります。主練習のABC146 Cでは予算内で買える最大の整数を「最後のtrue」として探し、次のABC023 Dでは許容する最大高度の実行可能性を「最初のtrue」として探します。
境界を探す判定を先に作る
候補に順序があり、ある位置を境に判定結果が変わるなら、二分探索でその境界を探せます。例えばfalse、false、false、true、trueという並びなら、最初のtrueを探せます。true、true、true、false、falseという並びなら、最後のtrueを探せます。
判定が途中でtrueからfalseへ戻ったり、falseからtrueへ戻ったりするなら、捨てた半分のどこに答えがあるかを決められません。二分探索を使う前に、候補を一つ増やしたとき判定がどちら向きに変わり、その後に戻らない理由があるかを確認します。
最後のtrueと最初のtrueを同じ例で比べる
候補を0から8まで並べ、ok(n)がn <= 5でtrueになる独自の机上例を考えます。この例は公式サンプルではありません。
| 探す境界 | 初期の不変条件 | 判定の追跡 | 隣接後に返す値 |
|---|---|---|---|
| 最後のtrue | low=0はtrue、high=9はfalse |
mid=4はtrueなのでlow=4、mid=6はfalseなのでhigh=6、mid=5はtrueなのでlow=5 |
low=5 |
| 最初のtrue | low=-1はfalse、high=9はtrue |
mid=4はfalseなのでlow=4、mid=6はtrueなのでhigh=6、mid=5はtrueなのでhigh=5 |
high=5 |
どちらもhigh-low > 1の間だけmid=(low+high)//2を調べます。最後のtrueではtrueだったmidをlow側へ含め、最初のtrueではtrueだったmidをhigh側へ残します。区間を半開区間[low, high)として扱い、lowとhighの真偽を更新後も保つと、隣接した時点の端点が境界になります。
この違いを取り違えると、判定自体は正しくても一つ前または一つ後の値を出力します。問題を読むときは、最大の条件を探すのか、最小の条件を探すのかを、最後のtrueまたは最初のtrueという形へ言い換えてからコードを書きます。
ABC146 Cで最後のtrueを探す
ABC146 C Buy an Integerの公式問題文では、1以上109以下の整数Nの価格を計算し、予算X以下で買える最大のNを求めます。価格はA * N + B * d(N)で、d(N)はNの十進表記の桁数です。買える整数がなければ0を出力します。
| 項目 | 公式の条件 |
|---|---|
| 入力 | A B X |
A、B |
1 <= A <= 10^9、1 <= B <= 10^9 |
X |
1 <= X <= 10^18 |
| 販売対象 | 1 <= N <= 10^9 |
| 出力 | 予算内で買える最大のN。存在しなければ0 |
価格の判定が単調になる理由
Nを1増やすとA * NはAだけ増えます。十進表記の桁数d(N)は減らず、9から10のような桁境界では増えます。AとBは正なので、価格A * N + B * d(N)はNに対して単調非減少です。
したがって、price <= Xを「買える」と判定すると、あるNが買えないなら、それより大きい候補も買えません。trueが続く範囲の最後を求める判定になり、二分探索でfalseになったmidより大きい側をhighへ捨てられます。
9と10をまたぐ独自例で更新を追う
独自の入力（公式サンプルではありません）として、A=10、B=7、X=99を使います。桁境界の近くを小さく追えるよう、候補0〜10を含む区間で同じ判定を実行し、初期状態をlow=0、high=11と置きます。low=0は購入可能な整数がないときも答えにできる真側の番兵、high=11はこの追跡で調べない偽側の端点です。完全コードは販売上限まで調べるためhigh=10^9+1から始まりますが、真偽を保ってmidを更新する規則は同じです。
| low | high | mid | 価格計算と判定 | 更新 |
|---|---|---|---|---|
0 |
11 |
5 |
price=10*5+7*1=57。1桁なのでprice <= X |
low=5 |
5 |
11 |
8 |
price=10*8+7*1=87。1桁なのでprice <= X |
low=8 |
8 |
11 |
9 |
price=10*9+7*1=97。1桁なのでprice <= X |
low=9 |
9 |
11 |
10 |
price=10*10+7*2=114。2桁になりprice > X |
high=10 |
最後の行の更新後はlow=9、high=10で隣接します。N=9の価格97はprice <= X、N=10は桁数が2になって114で予算外です。したがってこの独自例の最後のtrueは9であり、価格計算からlow／highの更新、出力までを一続きで追えます。
番兵と半開区間を固定する
コードではlow=0をtrueの番兵、high=10^9+1をfalseの番兵にします。0は販売対象外ですが、買える整数が一つもない場合に答えとして出力できるよう、判定を拡張してtrue側へ置きます。10^9+1は販売範囲の外に置く偽の境界で、high自身は判定しません。
不変条件は「lowはtrue、highはfalse」です。price <= Xならmidをtrue側のlowへ移し、そうでなければfalse側のhighへ移します。high-low > 1の間だけmidを取り、隣接したらlowを出力すると、lowは買える範囲の最後の値になります。
ABC146 Cの公式サンプル
次の4組は公式問題ページの入力例1から入力例4に掲載されている入力と出力です。独自の追跡例や境界確認とは分けています。
| 公式例 | 入力 | 出力 |
|---|---|---|
| 入力例1 |
|
|
| 入力例2 |
|
|
| 入力例3 |
|
|
| 入力例4 |
|
|
完全なPython参考コード
ABC146 Cの公式Editorialが示す単調性と二分探索を、標準入力から標準出力までつながる形にしています。これは教育用の参考コードであり、提出記録やACを示すものではありません。
A, B, X = map(int, input().split())
low = 0
high = 10**9 + 1
while high - low > 1:
mid = (low + high) // 2
price = A * mid + B * len(str(mid))
if price <= X:
low = mid
else:
high = mid
print(low)入力したA、B、Xを使い、各midの価格をlen(str(mid))で計算します。買えるmidはlowへ残し、買えないmidはhighへ移すため、コードの更新先は先ほどの不変条件と一致します。
コードの正しさを三つの条件で追う
- 価格が単調非減少なので、買えないmidより大きい候補はすべて買えず、high側へ捨てられます。
- 買えるmidは最後のtrueの候補なのでlow側へ含め、買えないmidはhigh側へ残します。
- 更新後もlow=true、high=falseを保ったまま区間幅が縮みます。隣接したときのlowが最大の購入可能値で、購入可能な整数がなければ番兵0が出力されます。
桁境界とoff-by-oneを確認する
high=10^9+1により、上限10^9を候補として確認できます。high自身は候補外の偽番兵なので、判定せずに残します。high-low > 1のときだけmidを計算するため、lowとhighが隣接した時点で探索を止め、最後のtrueであるlowを出力します。- N=0は販売対象ではありません。low=0、high=1のように隣接するとループが終わるため、0をmidとして価格計算せず、買える値がない場合の答えとして残せます。
- 9から10へ進むと
len(str(N))が1から2へ変わります。価格の増加幅が変わっても桁数は減らないため、単調性は保たれます。
計算量
探索は候補範囲を半分ずつ縮め、判定回数はO(log 10^9)です。各判定で扱う十進表記は最大10桁なので、このコード全体の計算量はO(log 10^9)と表せます。追加メモリはO(1)です。この計算量はコードのループに対応するもので、実行時間や性能を保証するものではありません。
ABC023 Dで最初のtrueへ切り替える
最大の購入可能Nを探す形から、最小の実行可能な最大高度を探す形へ移る練習として、ABC023 D 射撃王の公式問題へ進みます。ここでは候補となる最大高度limitを一つ決め、その高さ以下で全風船を割れるかを判定します。
風船iの初期高度をH_i、上昇速度をS_iとすると、H_i > limitなら開始時点ですでに上限を超えるため不可能です。そうでなければ、整数の締切を(limit - H_i) // S_iで求めます。締切の早い風船から割る順に並べ、0秒から始まる時刻0, 1, ..., N-1で、並べた締切がそれぞれの時刻以上なら実行可能です。
小さい風船例でlimitから最初のtrueまで追う
独自の入力（公式サンプルではありません）として、次の3個を使います。入力の上から風船A、B、Cと呼びます。
3
1 1
5 2
6 2この入力では、コードの初期値がlow=-1、high=max(1+1*3, 5+2*3, 6+2*3)=12です。high側を実行可能な番兵として置き、midの候補limitを判定します。締切は各行の(limit-H_i)//S_iで計算し、並べ替えた後の時刻timeは0から始めます。
| 判定前の区間 | 候補limit | 締切の計算・並べ替え | 判定と更新 |
|---|---|---|---|
low=-1, high=12 |
mid=5 |
CはH=6 > limit=5なので、締切を作る前に不可能 |
false、low=5 |
low=5, high=12 |
mid=8 |
A・B・Cの締切は7, 1, 1、昇順で1, 1, 7 |
time=0: 1 >= 0、time=1: 1 >= 1、time=2: 7 >= 2。true、high=8 |
low=5, high=8 |
mid=6 |
A・B・Cの締切は5, 0, 0、昇順で0, 0, 5 |
time=0: 0 >= 0の後、time=1: 0 < 1。false、low=6 |
low=6, high=8 |
mid=7 |
A・B・Cの締切は6, 1, 0、昇順で0, 1, 6 |
time=0: 0 >= 0、time=1: 1 >= 1、time=2: 6 >= 2。true、high=7 |
limit=7がtrueになった後はlow=6、high=7で隣接するため、high=7がこの独自例で最初のtrueです。H_i > limitの早期判定、締切の整数除算、締切順、0始まりのtime、deadline >= timeの各条件が、初期区間から結論までつながっています。
公式の制約は1 <= N <= 100000、1 <= H_i, S_i <= 1000000000です。
判定の向きと不変条件を変える
limitを大きくすると各風船の締切は厳しくならないため、あるlimitで可能なら、それ以上のlimitでも可能です。ABC146 Cの価格判定はtrueが続く範囲の最後を探しましたが、ABC023 Dの実行可能性はfalseが続いた後の最初のtrueを探します。
このコードの不変条件は「low=-1は不可能、highは可能」です。high=max(H_i + S_i * N)は、各風船についてH_i + S_i * N以上の高さを許す上限なので、締切が少なくともNとなり、high側の実行可能性を置けます。可能なmidはhighへ、不可能なmidはlowへ移し、隣接後にhighを返します。
完全なPython参考コード
ABC023 Dの公式Editorialが示す、候補高度、整数締切、締切順の判定を使った参考コードです。ABC146 Cとは判定関数と返す端点が変わります。こちらも提出記録やACを示すものではありません。
N = int(input())
balloons = [tuple(map(int, input().split())) for _ in range(N)]
def feasible(limit):
deadlines = []
for height, speed in balloons:
if height > limit:
return False
deadlines.append((limit - height) // speed)
deadlines.sort()
return all(deadline >= time for time, deadline in enumerate(deadlines))
low = -1
high = max(height + speed * N for height, speed in balloons)
while high - low > 1:
mid = (low + high) // 2
if feasible(mid):
high = mid
else:
low = mid
print(high)feasibleは候補limitごとに締切を作り、早い締切から並べます。enumerateのtimeは0から始まるため、最初に割る風船は時刻0、最後の風船は時刻N-1です。締切が時刻より小さいものが一つでもあれば、そのlimitでは割り切れません。
締切の早い順で判定できる理由
締切の早い順で十分なのは、実行可能な順番にある逆転を隣り合う2個ずつ交換しても、締切違反が起きないからです。時刻time=tに締切の遅い風船B、その次のt+1に締切の早い風船Aがあり、deadline_A <= deadline_Bとします。元の順番が実行可能なら、Aはt+1に割れるのでdeadline_A >= t+1です。したがってdeadline_B >= deadline_A >= t+1でもあり、Aを時刻t、Bを時刻t+1へ交換しても両方の締切を守れます。
この交換を逆転がなくなるまで繰り返すと、実行可能な順番を締切の昇順へ変えられます。だから、締切順に並べた配列でどこかのdeadline < timeが起きるなら、別の順番にしても全風船を割れる実行可能な順番はありません。反対に、並べた配列のすべてでdeadline >= timeなら、その配列自体が実行可能です。コードのdeadlines.sort()とall(deadline >= time ...)は、この十分性と必要性をそのまま判定しています。
ABC023 Dの公式サンプル
次の2組は公式問題ページの入力例1と入力例2に掲載されている入力と出力です。
| 公式例 | 入力 | 出力 |
|---|---|---|
| 入力例1 |
|
|
| 入力例2 |
|
|
公式の制約は1 <= N <= 100000、1 <= H_i, S_i <= 1000000000です。limitを整数ごとに1ずつ試す素朴解では、コードのfeasible(limit)を候補ごとに呼び、max(H_i + S_i * N)までの広い範囲を繰り返し調べます。1回の判定だけでもN個の締切を作ってソートするためO(N log N)かかり、候補を総当たりするとこの処理を候補数だけ繰り返すことになります。掲載コードは同じ判定を外側の二分探索でO(log U)回（Uは設定した高度上限）に抑えるので、全体がO(N log N * log U)になります。
締切の境界と計算量
H_i > limitを先に判定します。これを飛ばして割り算すると、上限を超えた風船に負の締切を割り当てることになります。(limit - H_i) // S_iは整数時刻の締切です。例えば締切0なら開始時刻に割る必要があり、最後の時刻は0始まりなのでN-1です。- 締切を昇順に並べた後のi番目は時刻iに割るため、判定は
deadline >= timeです。ABC146 Cの最後のtrueの更新をそのまま流用せず、可能側の最初のtrueをhighへ残します。
一回のfeasibleは締切のソートにO(N log N)かかり、判定回数は設定した高度上限Uに対してO(log U)です。全体はO(N log N * log U)、追加メモリはO(N)です。公式Editorialは同型の上限を用いてO(N log N * log(H+NS))として説明しています。
別の問題へ移す前に固定する項目
二分探索の形だけを覚えて別の問題へコピーすると、判定の向きや時刻の起点を取り違えます。実装前に、次の対応だけを問題ごとに書き換えます。
| 固定する項目 | ABC146 C | ABC023 D |
|---|---|---|
| 探す値 | 買える最大のN | 実行可能な最大高度limitの最小値 |
| 判定 | A * N + B * d(N) <= X |
limit以下で全風船を割れるか |
| 単調性 | 価格はNに対して増え、買えない側が後ろへ続く | limitが大きいほど可能性が保たれる |
| 不変条件 | low=true、high=false | low=false、high=true |
| 返す端点 | 最後のtrueであるlow | 最初のtrueであるhigh |
次に最大値・最小値の問題へ取り組むときは、判定関数を一文で書き、trueとfalseの境界、番兵の意味、midを更新する側、隣接後に返す端点を確認します。ABC146 CからABC023 Dへの移行では、価格からスケジュール可能性へ判定を変え、最後のtrueから最初のtrueへ不変条件を反転し、0始まりの射撃時刻をdeadline >= timeへ対応させます。
出典はABC146 C公式問題文、ABC146公式Editorial PDF、ABC023 D公式問題文、ABC023公式Editorial PDFです。
