答えに対する二分探索
結果を推測し、実現可能性を確認します
「答えに対する二分探索」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
推測してから検証する
答えを直接計算できなくても、推測を検証できる場合があります。答えに対して二分探索を行うと、難しい最適化問題を簡単な検証問題に変えられます。
# guess X, ask: is X feasible?魔法のような性質
これは、実行可能性が単調な場合に機能します。ある値で可能なら、それより大きい値（または小さい値）でもすべて可能になるという性質です。探索するのはこの順序です。
# feasible(X) true => feasible(X+1) true答えの範囲を限定する
可能な答えの最小値と最大値を low と high として特定します。最小容量を求める場合、low は一つの要素の値、high は合計値です。
low, high = max(weights), sum(weights)実行可能性のチェックを書く
この手法の中心は、推測した X が実現可能なら true を返す can(X) 関数です。通常は線形時間で実行できます。
def can(cap):
# simulate and return True/False
...D 日で発送する例
1 日あたりの容量 cap が与えられたら、貪欲に各日の荷物を埋めて日数を数えます。can(cap) は、必要な日数が上限 D 以内なら true になります。
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= D最小容量を探索する
条件を満たす最小の cap を求めます。これは容量に対するfirst-true 探索なので、high = mid のテンプレートを再利用してください。
while low < high:
mid = (low + high) // 2実行可能な半分を残す
can(mid) が true なら、もっと小さい容量でも可能かもしれないので、high = mid とします。そうでなければ low = mid + 1 として下限を引き上げます。
if can(mid):
high = mid
else:
low = mid + 1計算量の予算に注意する
全体のコストは O(check x log range) です。範囲が 10 億あっても、線形時間のチェックは約 30 回だけなので、厳しい制限時間でも十分に高速です。
# log2(1e9) is about 30 iterations最小化ではなく最大化する
最大の実行可能な値を求めるには、考え方を反転して最後の true を探索します。実行可能なら low を上げ、そうでなければ high を下げます。
if can(mid):
low = mid
else:
high = mid - 1実数の答え
実数の答えでは、整数の mid を使う代わりに、100 回のように回数を固定してループします。各回で区間が半分になり、すぐに非常に高い精度へ到達します。
for _ in range(100):
mid = (low + high) / 2パターンを見抜く
「最小の最大値」「最大の最小値」「条件を満たす最小の k」のような表現は、答えに対する二分探索の合図です。見抜く力を鍛えてください。
# 'minimize the maximum' => search answer確認
答えに対する二分探索をいつ適用できるか判断してください。
まとめ：答えを探索する
これで答えの範囲を定め、実行可能性のチェックを書き、最小値や最大値を二分探索できるようになりました。難しい問題も、推測して検証する問題に変えられます。🏆
よくある質問
「答えに対する二分探索」レッスンは無料ですか？
はい。「答えに対する二分探索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「答えに対する二分探索」で何を学びますか？
結果を推測し、実現可能性を確認します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「答えに対する二分探索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。