【atcoder】二分探索問題をマスターする

#記事背景#
　atcoder初心者のrib7です。atcoderで高成績を狙うには、ある程度コードのストックを持っておくことが大切だと思います。そこで今回は、二分探索問題のコード雛形を作成し、実際の問題への使い方を解説していきます。

#二分探索の概要#
　二分探索とは、真の値を素早く探索するために使う手法で、atcoderではD問題あたりでよく出題されています。例えば取引で相手の希望額を聞き出したい時に、「あなたの希望額は1千万円以上ですか？」→NO→「500万円以上ですか？」→YES→「750万円以上ですか？」→...とやっていけば、いつかは希望額を知ることができるというものです。「いや、最初から希望額はいくらか聞けばええやん！？」とツッコんだ貴方、まさにその通りです。しかし、往々にして問題中では、その値を直接知る術がないことがたくさんあります。例えば「ーーが成立する最小のーーを求めよ」というような時に、「境界は分からないけど、その値で成立するかどうかは計算可能」「その境界以上（以下）ではずっと同じ状態になる」といった時に抜群の効果を発揮します。先ほどの例でいうと、「希望額とかは分からないけど750万円以下じゃちょっと嫌」「825万円以上ならまぁええかな」みたいなふわっとした感覚を持った取引相手の時に有効というわけです。このように二分探索の問題では「この問題は二分探索で解ける！！」と考えて実装するまでが何より難しく、二分探索のコード自体はそこまで難しくありません。だからこそ、経験と知識が必要になるわけですね。

#二分探索のプログラミングコード#
　二分探索のコードを学習する上でベンチマークとしたのはatcoder典型90題の最初の問題["Yokan Party"][link-1] です。この問題の正解法はこのコードです（解説は下で行います）。参考にしたのは["公式解答"][link-2]です。

[link-1]:https://atcoder.jp/contests/typical90/tasks/typical90_a
[link-2]:https://github.com/E869120/kyopro_educational_90

```c++:binary_search.cpp
#include <iostream>
#include<vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int K, N, L;
vector<int> A(100000000);

//二分探索のコード
//関数judgeによりその値が条件を達成するかを確認する
//このコードは典型90問1問目のYokanPartyをベースとしている

bool judge(int m) {
	int count = 0, H = 0;
	for (int i = 0; i < N; i++) {
		if (A[i] - H >= m && L - A[i] >= m) {
			count++;
			H = A[i];
		}
	}
	if (count >= K) { return true; }
	else { return false; }
}

int main() {
	cin >> N >> L >> K;
	rep(i, N) { cin >> A[i]; }

	int left = 0, right = L;
	int mid = (left + right) / 2;

	while (right - left > 1) {
		bool frag = judge(mid);
		if (frag)left = mid;
		else right = mid;
		mid = (left + right) / 2;
	}
	cout << mid;
}
```

#コードの解説#
　この問題を見た時、僕は最初とりあえず漸化式で解いていこうとしてしまいました（計算時間オーバーでした）。このような問題を二分探索で解こうという嗅覚が大切になるわけです。実はmain()関数の中身は二分探索の問題では大体同じで、変更する必要があるのはjudge()関数の実装です。今回のjudge()関数では「そのスコア以上でYokanを切れるかどうか」を判別しています。そのスコアでYokanが切れるなら→さらに高みを目指せるかどうか探索、そのスコアでYokanが切れないなら→どのスコアなら可能か探索、と制御していくのがmain()関数内のwhileの中身なわけですね。そして最終的には「そのスコアなら分割可能だけど、1でもスコアを上げてjudge()すると分割不可能になる」というスコアを真のスコアとしてcoutしている訳です。

#他の二分探索問題への適用#
　他の二分探索問題も原理は同じで、ある値でjudgeする→judgeがtrueであれば大きくして再度judge、judgeがfalseであれば小さくして再度judgeという作業を繰り返していき、最後にはjudgeがtrueになるかfalseになるかの境界を求めて答えとする、という問題が多いです。
参考問題１ [abc192-d][link-3] 
[link-3]:https://atcoder.jp/contests/abc192/tasks/abc192_d

<details><summary>サンプルコード</summary><div>

```c++:binary_search_2.cpp
#include <iostream>
#include<vector>
#include <math.h>
#include <string>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
long long M;
int d,K;
string X;

//二分探索のコード
//関数judgeによりその値が条件を達成するかを確認する
bool judge(long long q) {
	long long H=0, S = 1;
	if (q == 1) {
		return true;
	}
	int Z = log10(M) / log10(q);
	if (Z >= K) { Z = K-1; }
	int J = 0;
	for (int i = 0; i < Z+1; i++) {
		J = X[K-1-i] - '0';
		H += S * J;
		S *= q;
		if (H > M) { return false; }
	}
	for (int i = Z+2; i < K+1; i++) {
		int JO = X[i] - '0';
		if (JO!= 0) { return false; }
	}
	return true;
}

int main() {
	getline(cin, X);
	cin >> M;
	int q,aa=0;
	d = 0;
	K = X.size();
	for (int i = 0; i <= K; i++) {
		q=  X[i] - '0';
		if (q > d)d = q;
	}

	long long left = 0, right = M+1;
	long long mid = (left + right) / 2;
	if (K == 1&& X[0] - '0' <= M) {
		cout << 1;
		return 0;
	}

	while (right - left > 1) {
		bool flag = judge(mid);
		if (flag)left = mid;
		else right = mid;
		mid = (left + right) / 2;
	}
	if (left - d < 0) { left = d; }
	cout << left-d;
}
```
</div></details>

このように、入力部やjudge()関数内の内容は変わりましたが、コード構造自体は変わっていないことが分かると思います。また、二分探索を使うタイミングの基準として
①計算時間が問題となる
②状態１から状態２に遷移するタイミングが知りたい
の２つを追記しておきます。

#まとめ#
　いかがだったでしょうか。二分探索問題は「この問題は二分探索の問題だ！」と認知するのが何よりも難関で、プログラミングコード自体は上で挙げたようなコードを改造して作っていけばよいわけです。そのための嗅覚や改造の方法をこの記事の中で学んでいただけたなら幸いです。