　皆様は二分探索をバグらせたことはありますか。私はあります。本日は、そのような苦い経験をもとに、時間はかかるけど、思考停止で書けて絶対にバグらない二分探索法「サンプルケース駆動型二分探索法」を提唱したいと思います。

概要

　本手法は以下のような手順からなります。

サンプルケースがokとなるようなプログラムを書く
for文を書いてサンプルケースと境界が一致することを確認する
for文をwhileに直すことにより二分探索化する

　特に重要となるのが 2. の手順で、ここで「以上と未満を間違えていないか」「判定ロジックが正しいか」等を検証できます。本手法は真面目にやると時間がかかるので、

難問をゆっくり解きたい時
コンテンスト中でも絶対にWAを出したくない時
もう頭を使うことに疲れた時

　等に活用できると思います。

実例1 簡単な二分探索

　ABC146 C - Buy an Integer を元に解説していきます。

1 サンプルケースがokとなるようなプログラムを書く

　以降、includeやマクロ等は省略します。

　競プロの問題では、問題文の理解を助けるために、簡単な例をサンプルケースとして公開しているのが普通です。これをそのまま利用します。

ll d(ll n)
{
    ll ans = 0;
    while (n > 0)
    {
        ans++;
        n /= 10;
    }
    return ans;
}

int main(void)
{
    ll a, b, x;
    cin >> a >> b >> x;
    ll target = 9; // 何も考えずにサンプルケースの出力を入れる
    ll price = a * target + b * d(target);
    cout << price << endl; // debug 97
    if (price <= x)
    {
        cout << "ok" << endl;
    }
    else
    {
        cout << "ng" << endl;
    }
}

　okが出力されて、priceが97であることからロジックも正しいことがわかります。このように、段階的にデバッグを挟むことでバグを逐一潰すことができます。

2 for文を書いてサンプルケースと境界が一致することを確認する

　さて、いよいよ本手法のキモです。今書いたプログラムを改造して、targetをfor文で回していきます。

int main(void)
{
    ll a, b, x;
    cin >> a >> b >> x;
    rep(target, 20) // step2 で追加
    {
        // ll target = 9; step2 でコメントアウト
        ll price = a * target + b * d(target);
        // cout << price << endl; step2 でコメントアウト
        if (price <= x)
        {
            cout << target << " ok" << endl;
        }
        else
        {
            cout << target << " ng" << endl;
        }
    }
}

　すると以下のような出力がされます。

0 ok
1 ok
2 ok
3 ok
4 ok
5 ok
6 ok
7 ok
8 ok
9 ok
10 ng
11 ng
12 ng
13 ng
14 ng
15 ng
16 ng
17 ng
18 ng
19 ng

　サンプルケースの正解である9を境界にきっかりokとngが分かれており、ロジックが正しいことが確認できます。逆に、ここでokとngが入り交じるようであればロジックがおかしい可能性が高く、境界が 1 つズレているような場合は、「以上」や「未満」の扱いを間違えている可能性が高いです。

　最悪、ロジックを理解していなくても、サンプルケースでちょうどokになるようにコードを微調整していけば正解できる可能性は高いです。「問題文で問われている条件の本質は何か……！？」みたいなことを考える必要もないです。（もちろん、それを考えた上で正解できるのが一番です）

3 for文をwhileに直すことにより二分探索化する

　for文で正しい答えが求められるならば、後はするべきことは二分探索化して高速化することだけです。

　しかし、二分探索を組むにあたってバグりやすいポイントが一つあります。下端がtrueになるか上端がtrueになるかです。実は上の検証リストからわかる重要な情報として、targetが0の時にokになっているかそうでないかがあります。これをそのままコピーすればいいのです。

int main(void)
{
    ll a, b, x;
    cin >> a >> b >> x;
    ll ok = -1;               // step3 で追加。リストでok側になってる方
    ll ng = 1e9 + 1;         // step3 で追加。リストでng側になってる方
    while (abs(ok - ng) > 1) // step3 で追加
    // rep(target, 20) // step3 でコメントアウト。
    {
        // ll target = 9; step2 でコメントアウト
        ll target = (ok + ng) / 2;
        ll price = a * target + b * d(target);
        // cout << price << endl; step2 でコメントアウト
        if (price <= x)
        {
            // cout << target << " ok" << endl;
            ok = target;// step3 で追加
        }
        else
        {
            // cout << target << " ng" << endl;
            ng = target;// step3 で追加
        }
    }
    cout << ok << endl;
}

　これで正解できます。

実例2 難しい二分探索

　上に述べたようなことは「わざわざステップに分けて考える必要があるのか？」と思った方もいるとは思います。何を二分探索するかがあきらかな時はその必要はあまりないかもしれません。このようなステップ化が力を発揮するのはより難しい二分探索、具体的には決め打ち二分探索といった例です。

　D - Widespread を例に解説していきます。

　ぱっと見二分探索っぽくはないですが、答えを決め打ちすることで二分探索できるという問題です。二分探索を使うであろうとアタリをつければ、サンプルケースがまずは決め打つべき値になります。

1 サンプルケースがokとなるようなプログラムを書く

bool solve(ll target, vector<ll> h, ll n, ll a, ll b)
{
    rep(i, n)
    {
        h[i] -= b * target;
    }
    a -= b;
    ll count = 0;
    rep(i, n)
    {
        if (h[i] <= 0)
        {
            continue;
        }
        count += (h[i] + a - 1) / a;
    }
    if (count <= target)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }
    ll target = 2;
    if (solve(target, h, n, a, b))
    {
        cout << "ok" << endl;
    }
    else
    {
        cout << "ng" << endl;
    }
}

　この記事ではsolveの部分に正しいコードを買いていますが、実際に問題を解く段階では、最初から正しいコードを書くことは難しく、手探りで書いていくことになります。

　しかし、この段階で適当なコードを書いてしまっても、次の step2 でロジックの検証ができるので、とりあえずこの段階ではokを出すことだけを考えましょう。テストケース駆動型開発みたいですね。実際に決め打ちの値を設定して考えることによって、具体的な考察が進みやすくなるのもこの手法のメリットかなと思います。

2 for文を書いてサンプルケースと境界が一致することを確認する

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }
    rep(target, 10)
    {
        if (solve(target, h, n, a, b))
        {
            cout << target << " ok" << endl;
        }
        else
        {
            cout << target << " ng" << endl;
        }
    }
}

0 ng
1 ng
2 ok
3 ok
4 ok
5 ok
6 ok
7 ok
8 ok
9 ok

　この問題では別のサンプルケースも公開されているので、それも試してみます。

0 ng
1 ng
2 ng
3 ng
4 ok
5 ok
6 ok
7 ok
8 ok
9 ok

　大丈夫そうです。

3 for文をwhileに直すことにより二分探索化する

　次にwhile文に直していきます。今度は0側がngであることに注意します。

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> h(n);
    rep(i, n)
    {
        cin >> h[i];
    }
    ll ng = -1;
    ll ok = 1e9 + 1;
    while (abs(ng - ok) > 1)
    // rep(target, 10)
    {
        ll target = (ok + ng) / 2;
        if (solve(target, h, n, a, b))
        {
            // cout << target << " ok" << endl;
            ok = target;
        }
        else
        {
            // cout << targt << " ng" << endl;
            ng = target;
        }
    }
    cout << ok << endl;
}

　これで正解できます。

まとめ

　実際にこのようにコードを書き直すかはともかく、

サンプルケースがokとなるようなプログラムを書く
for文を書いてサンプルケースと境界が一致することを確認する
for文をwhileに直すことにより二分探索化する

　ことは、決め打ち二分探索等の複雑の問題を解く際の有用な手順となると思われます。