AIで解説 AtCoder攻略　二分探索

二分探索ページの位置づけ

項目	内容
必修度	重要
学習目安	標準
前提	単調性・判定関数
対象問題	48問（推定値あり48問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	1
標準	0〜799	14
標準〜発展	800〜1199	7
発展	1200以上	26
未算出	—	0

判定可能な条件を単調性に変換し、二分探索で境界や最大値を求めるページです。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

二分探索の見分け方

条件を満たす値の範囲が連続している
最小・最大の境界を探す
feasibilityを判定して候補を絞る

二分探索の実装前チェック

探索範囲と判定の真偽を決める
境界の更新を1行で説明できるか確認する
空区間・端点の扱いを確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC146 C Buy an Integer（公式解説）を解きます。買える整数Nを「買える／買えない」の境目で二分探索します。桁数が増えても必要な金額は単調に増えるため、判定関数を使えます。

A, B, X = map(int, input().split())

low, high = 0, 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)

1から上限まで試すとO(10^9)回ですが、二分探索ならO(log 10^9)回の判定です。

二分探索の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC434 A Balloon Trip	公式解説	公式Editorialの方針を balloon trip binary search として整理する。	-1206
ABC231 C Counting 2	公式解説	ソート済み得点列でX以上の最初の位置を二分探索し、残りの個数を返す。	111
ABC365 C Transportation Expenses	公式解説	Official editorial intent is classified as budget binary search.	241
ABC198 C Compass Walking	公式解説	Use one straight move when the distance is at most R, otherwise use two perpendicular moves with ceiling checks.	413
ABC195 B Many Oranges	公式解説	Find the minimum and maximum integer number of oranges satisfying both weight bounds, or report impossible.	483

次に解く

問題	公式解説	出題意図	difficulty
ABC437 C Reindeer and Sleigh 2	公式解説	Sort reindeer weights, build prefix sums, and binary-search the largest feasible group.	489
ABC319 D G. Minimum Width	公式解説	Binary-search the minimum width and greedily pack sorted points into intervals.	631
ABC415 C Mixture	公式解説	公式Editorialの方針を mixture binary search として整理する。	657
ABC457 D G. Raise Minimum	公式解説	Binary-search the minimum raised value and check feasibility greedily.	677
ABC299 D G. Find by Query	公式解説	単調な応答を利用して境界位置を二分探索で特定する。	684

挑戦問題

問題	公式解説	出題意図	difficulty
ABC205 D Kth Excluded	公式解説	Binary-search the smallest x for which x minus the number of excluded values ≤x reaches each query K.	713
ABC144 D Water Bottle	公式解説	傾けた角度に対して入る水量が単調になることを使い、断面積の場合分けと二分探索で角度を求める。	714
ABC312 C Invisible Hand	公式解説	Binary-search a price where the number of sellers and buyers crosses.	727
ABC146 C Buy an Integer	公式解説	桁数を含む価格判定の単調性を利用し、予算内で買える整数の最大値を二分探索する。	741
ABC279 D G. Freefall	公式解説	Minimize A/√(x+1)+Bx over integer x using convex search and neighboring candidates.	766