二分探索を極める ~ 判定問題を完全攻略 #1

Last updated at 2025-09-09Posted at 2025-09-09

前提知識

二分探索がなぜ３でも４でもなく、２で分割するかを説明できる

解答例：走査対象の集合を一意に並び替える手法が、二値判定に依存するためです。配列が予め合格判定と同様の条件で整順されているから、検索対象の値が属し得る区間ごとの判別できます。

(尚、三分探索も存在しますが、この記事では触れません。)

ネタバレ注意

この記事は一部のAtCoder出典問題の解法のネタバレを含みます。

1. 二分探索を極めるとは

二分探索が想定解の問題に対しての考察力を上げることを目的とします。具体的には、任意の条件を満たす値を良い感じに探す力を上げるために、何が出来るかを知りましょう。

2. 条件の設定とは具体的には何か

一般的には、二分探索を利用する際は、累積和のlower_boundを辿るなど、予め作られた配列を探索するような形を取ると思います。

ただ、値の取りうる範囲を配列と見做して、それを探索することで判定を満たす値を探す手法もあります。考察の過程で、計算式で必要な入力値と解を表せたとしても、何らかの理由で式変形できない時などに有効です。

ただ、二分探索はどの判定問題にも使える訳ではなく、勿論制約がつきます。以下の要件を満たしていないと、上手く使えません。

必要条件

一度に求められる解は一つだけである
解となる数値を求める式が存在する
解を求める関数の変化の具合が線形である

ただ、これを満たすだけで、面倒な組み合わせを無視して$O(logN)$で求められちゃうのです。細かい判定条件は、区間更新の指定などで、幾らでも実装できちゃいます。具体的な話の前に、汎用的な実装指針について振り返ろうと思います。

3. 区間更新について

二分探索の関数を適当に書くと、無限ループを引き起こしたり、求めたい値に辿り着くか確証が持てなかったりしませんか？ここで、二分探索の挙動の謎を解明しましょう。

ここで大事になってくるのが半開区間という概念です。基本的に左と右のどちらからも詰めるという手法を取ります。対する閉区間のような、どちらも解に該当するような不安定な書き方をせずに、どちらかを解に一致させるように決めてしまえばいいのです。目的に応じてどちらを取るかを柔軟に変える必要があることは念頭におきましょう。

下のは、$[l, r)$ (左側を解とする時)の実装例 (C++)です。

auto binarysearch = [&](int k) {
    int l=0, r=N; //rは配列の最上値のN-1の一つ上を設定する
    
    while(l+1 < r) { //[l, r)の走査条件の時には、l+1==rの時に解が定まるから
        int m = l+(r-l)/2;
        if(v[m]<=k) l=m; //解をlに設定するために判定条件を「以下」に設定する
        else r=m;
    }
    return l; //lをちゃんと返す
};

これで、実装や解説記事を見る際に、実装方針がブレることが無くなったのではないでしょうか？
実際、次の章で記す「独自の判定式」を構築する必要がある二分探索において、条件設定を理解することは極めて重要なので、しっかり押さえましょう。

4. 判定問題を攻略する

十分な説明をしたので、練習問題に取り組んでみましょう。

例１ ABC023D - 射撃王 (青diff)

この問題は「最小値」を求める問題です。もうちょっと良く読んでみると、質問は「全てを打ち落とす」という明確な条件のもとの「最小値」を聞いています。「与えられた高さのもとで、全てを打ち落とせるか」は、各風船を探索することで簡単に求まります。
故に、比較演算子を置き換えて、探索範囲である$l$と$r$をしっかり設定したら、もうACです。具体的には、範囲指定を適当に$(0,$inf$]$とすると、判定関数の挙動が不安定になるので、気を付けましょう。

二分探索のコード例 (C++)

// 判定関数
auto possible = [&](ll x) {
    vector<int> tcnt(N, 0);
    for(int i=0; i<N; ++i) {
      //t=最大許容時間　これがNに収まりきらないと不正
      if(x<h[i]) return false;
      int t = min((x-h[i])/s[i], N-1LL);
      tcnt[t]++;
    }
    int pcnt=0;
    for(int i=0; i<N; ++i) {
      pcnt += tcnt[i];
      if(pcnt> i+1) return false;
    }
    return true;
  };
//最小値を求めているので(l, r]区間で走査する
auto binarysearch = [&]() {
    ll l=maxih-1, r=maxlh;
    while(l<r-1LL) {
      ll m = l+(r-l)/2LL;
      if(!possible(m)) l=m;
      else r=m;
    }
    return r;
};

cout << binarysearch() << endl;

提出リンク：こちら

例2 ABC341D - Only one of two (緑diff)

難易度としては例1を下回りますが、この問題が判定問題の本質を見事に捉えている為、起用しました。問題が掲示している解の条件を式に展開すると、解を$X$とした時に$X = \lfloor{\frac{X}{N}}\rfloor+\lfloor{\frac{X}{M}}\rfloor-2\times\lfloor{\frac{X}{LCM(M, N)}}\rfloor$となります。二分探索を使う必要条件を満たしてはいますが、不適切な区間更新では、解が$M$か$N$の倍数を選んでくれません。
そこで、探索範囲が解の区間に辿り着いた後に切り捨て空間で遊ばせる発想に至ります。式の条件を満たしたうえで、更にその最小値を選び抜くことで、見事、解の条件を無駄な所作なく求められてしまうのです。これぞ、二分探索の真骨頂です。