思考停止で書けて絶対にバグらない（時間はかかるけど）！　サンプルケース駆動型二分探索法

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

# 概要

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

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

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

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

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

# 実例1 簡単な二分探索

　[ABC146 C - Buy an Integer](https://atcoder.jp/contests/abc146/tasks/abc146_c) を元に解説していきます。

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/04ae640f-a4f5-36c8-e340-aa1d0f36fc8b.png)


```C#
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`文で回していきます。

```c++
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;
        }
    }
}
```

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

```c++
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`になっているかそうでないか**があります。これをそのままコピーすればいいのです。

```c++
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](https://atcoder.jp/contests/arc075/tasks/arc075_b) を例に解説していきます。

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/a8bd4c26-3b93-104f-9b9e-7a0ec6d5b0a2.png)

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

```c++
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文を書いてサンプルケースと境界が一致することを確認する

```c++
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;
        }
    }
}
```
```c++
0 ng
1 ng
2 ok
3 ok
4 ok
5 ok
6 ok
7 ok
8 ok
9 ok
```

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/8d2e62c8-5258-633f-4de5-ef83952b2103.png)

```c++
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`であることに注意します。

```c++
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;
}
```

　これで正解できます。

# まとめ

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

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

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