概要
競技プログラミングを解いていてよく出てくる単語「全探索」についてまとめています。自分のメモ程度ですが、参考になれば幸いです。
これから、アルゴリズム入門に動的計画法とかダイクストラ法とかも乗っけていきます。コード例も書いていって書いていくうちにAtCoderのレートも上がっていくという好循環。基本的にネットやQiitaで得た知識をまとめていくだけのものです。
言語は慣れているjavaを使いますがまぁなんでも良いです。
全探索とは
名前でわかると思いますが、「考えうる全ての可能性」を考えるのが全探索だと思っています。なかにはいろいろ種類があるみたいで、その種類ごとに問題とコード例を考えてみましょう。
全探索の種類は以下のとおりっぽいです。
- 全探索
- 二分探索（バイナリサーチとも）
- 深さ優先探索（DFSとも）
- 幅優先探索（BFSとも）
- bit全探索
とりあえずこれだけわかれば良さそう。
一つ一つ例題とともに見ていこうと思います。
探索アルゴリズムの説明とコード例
ひとつひとつ解説していきます。
全探索
ありうる回答をすべてfor文のネストで調べることです。
簡単ですね。例題を見ていきましょう。
問題はなるべく簡単な問題を解いていくこととします。そのほうがわかりやすい & 僕が簡単なものでないと解けないためです。
【問題文】（ちょっと簡単に書いてます。）
整数Nが与えられるので、Nが1以上9以下の整数の積であらわせるかどうか判定し、表せるなら"Yes",表せないなら"No"を出力せよ。
【制約】
1≦N≦100, Nは整数
【回答例】
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
// Nが条件に合致するかどうかのフラグ
boolean flg = false;
// i * j = N となるようなi,jを全探索する
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
if (i * j == N) {
flg = true;
break;
}
}
if (flg) {
break;
}
}
if (flg) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
こんな感じです。
for文を二重にネストさせて九九の全てのパターンを全て探索しています。
全探索の注意点は、計算量が多くなることです。
今回は九九だったので、最悪のケースでも9^2 = 81回のループで済みましたが、例えば九九でなく10^5までの掛け算の積とか言われてしまったら、10^5 * 10^5 = 10^10の計算量がかかって時間がかかってしまうことに注意しましょう。
二分探索
当てはまるものを全体の前半か後半の集団にあるかどうかを繰り返すやり方です。
例えば、Aさんという人に「1から11までで、私の好きな数字はなんでしょう？」と聞かれたとします。こちらの質問に対してAさんは質問した数字より大きいか小さいか、またはそれが答えかを答えてくれるとしましょう。このときに、なにも考えない単純な全探索だと、「1ですか？」「2ですか？」・・・、と1~11までを順番に聞いていき、最悪な場合11回の質問が必要になります。計算量で言うとO(N)回ですね。
これを二分探索で行うと以下のような感じです。Aさんのこたえは10としましょう。
1:あなた「(1と11の中間)6ですか？」 Aさん「6よりも大きいです。」
2:あなた「(6と11の中間)9ですか？」 Aさん「9よりも大きいです。」
3:あなた「(9と11の中間)10ですか？」 Aさん「あたりです。」
と、このように、たった3回の質問で答えにたどり着けましたね。
集団のちょうど中間の値から初めて、一回の質問ごとにその集団の前半に答えがあるか、後半に答えがあるかを判定しています。
以下の図がわかりやすいかもしれません。
一回の質問ごとに範囲がどんどん半分になっていくので、11個しか候補がない場合は、多くとも4回の質問（2^4 = 16）で済んでしまうことがわかると思います。計算量で言うとO(logN)ですかね。
では、例題にいきましょう。
例：AtCoder - abc146-c「Buy an Integer」
【問題文】（引用）
高橋くんは整数を1つ買いに整数屋さんに行きました。
整数屋さんには 1以上10^9以下の整数が売られていて、整数Nを買うためには
A×N+B×d(N) 円が必要です。ここで、d(N)は Nの十進表記での桁数です。
高橋くんの所持金が X円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1つもない場合は0を出力してください。
【制約】
入力は全て整数。
1≤A≤10^9
1≤B≤10^9
1≤X≤10^18
【回答例】
import java.util.Scanner;
public class Main {
static long A;
static long B;
static long X;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
A = sc.nextLong();
B = sc.nextLong();
X = sc.nextLong();
long max = 1000000000l + 1l;
long min = 0l;
// 二分探索
for (;;) {
// 2数値の平均値
long mid = (max + min) / 2;
if (canSolve(mid)) {
// 平均値で解けるなら後半の半分で探索
min = mid;
} else {
// 平均値で解けないなら後半の半分で探索
max = mid;
}
if (max - min <= 1) {
// 二部探索終了
break;
}
}
System.out.println(min);
}
// 桁数取得
static long len(long num) {
return String.valueOf(num).length();
}
// 解けるかどうか
static boolean canSolve(long num) {
return A * num + B * len(num) <= X ? true : false;
}
}
当然ですが、この問題を単純な全探索で解こうとするとすべてのNで考えなければならず、Nは1以上10^9以下の整数のため、最悪の場合で10^9回処理をしなくてはなりません。というわけで二分探索の登場です。コードを見てわかるでしょうか。
long max = 1000000000l + 1l;
このあたりがちょっと難しいところですね。
javaのlongの割り算だと小数は切り捨てられるので、maxを1,000,000,000としてしまうと、
min:999,999,999、max: 1,000,000,000となったとき、midは999,999,999(=min)となってしまい、1,000,000,000について調べられなくなってしまいます。
あと単純に見やすさとメソッド分けが好きなので桁数取得と買えるかどうかの判定は外だししてますけどどっちでも良いです。
二分探索でこの問題を解きましたが、なんと言っても計算量が少ないことが利点だと思います。
この問題だと最悪のケースでも約30回ほどループさせれば答えにたどり着きます。
2^30が10^9より大きいので。
ただし二分探索は「ソートされている集団」にしか有用でないことは押さえておいた方が良さそうです。「連続した整数」とかだったら二分探索使えそうな気もしますね。
全探索、二分探索について勉強・解説していきましたがいかがでしたでしょうか。
深さ優先探索・幅優先探索・bit全探索についても同じ記事でやろうと思ったんですがのちのち見返しにくいなと思ったので記事をわけて投稿することにしました。
次回は深さ優先探索・幅優先探索について勉強・解説していきます。
お楽しみに。