全探索とは

第1回の記事ではプログラミングやアルゴリズムに関する能力を競う「競技プログラミング」を紹介し、アルゴリズム（問題を解く手順）の重要性について説明しました。今回からはいよいよ、具体的なアルゴリズムの解説に入っていきます。本稿では、最も単純なアルゴリズムであり、全ての基本でもある「全探索」について取り上げます。

第1回「競技プログラミングとは」はこちらから

全探索とは

全探索は、あり得る全てのパターンをしらみつぶしに調べることで問題を解くアルゴリズムです。4 桁の暗証番号を入力するときに、「0000」から「9999」まで 1 つずつ全部調べていくことを想像すると、直感的に理解しやすいかもしれません。全探索の簡単な例として、次の問題を考えてみましょう。

あなたは太郎君に対して、Yes/No で答えられる質問を 12 回まで行うことができます。

太郎君の誕生月を当ててください。

この問題を解く方法として、「誕生月は 1 月ですか？」「誕生月は 2 月ですか？」「誕生月は 3 月ですか？」といった順番で答えを聞いていくことが考えられます^※1。例えば太郎君の誕生月が 8 月の場合、下図のように 8 回の質問で答えを当てることができます。

このように、全探索では答えを出すために全てのパターンを調べます。

全探索で解ける問題の例

全探索は、プログラミングの問題でも使うことができます。例として、以下の問題を考えてみましょう。

赤・青のカードが各 1 枚ずつあり、あなたはそれぞれのカードに 1 以上 N 以下の整数を 1 つずつ書き込みます。カードに書かれた整数の合計が S 以下となるような書き方はいくつありますか。

例えば N=3、S=4 のケースでの答えは 6 となります。赤・青のカードに整数を書き込む方法として下図の 9 通りが考えられますが、そのうち合計が S（=4） 以下となるのは 6 通りだからです。

制約： 1 ≤ N ≤ 1000、1 ≤ S ≤ 2000

出典：アルゴリズムと数学 演習問題集 008 - Brute Force 1

この問題は、赤のカードに書く数 a を 1 ≤ a ≤ N の範囲で、青のカードに書く数 b を 1 ≤ b ≤ N の範囲で全探索すれば、答えを求められます。以下のように二重の for 文を使うことで、プログラムを実装できます。

なお、全探索で調べるべきパターンの数は N² 通り^※2なので、制約の上限である N=1000 でも 1000 の 2 乗、すなわち 100 万通りだけ調べれば答えを出すことが可能です。前回述べた通り、家庭用 PC の計算速度は毎秒 10⁸ ～ 10⁹ 回程度なので、1 秒以内に実行が終わりそうですね。

# 入力