第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 文を使うことで、プログラムを実装できます。

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

# 入力
N, S = map(int, input().split())

# 全探索
Answer = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        if a + b <= S:
            Answer += 1

# 出力
print(Answer)

このように、パターン数がそれほど多くないのであれば、プログラミングの問題でも全探索を使って解くことができる場合があります。

全探索で解けない問題

しかしながら、世の中の全ての問題が全探索で解けるわけではありません。例えば次の問題を考えてみましょう。

とあるコンビニには以下の 60 個の品物が売られています。500 円以内の買い物をするとき、最大で何 kcal を摂取することができますか。

商品 1 商品 2 商品 3 ...... 商品 60
値段 100 円 170 円 110 円 ...... 90 円
カロリー　 226 kcal　 368 kcal　 259 kcal　 ......　 205 kcal　

品物の数を n とするとき、品物の選び方は全部で 2n 通りあります。したがって、この問題では 260=1152921504606846976 通り（約 115 京通り）も調べなければならず、とても大変です。家庭用 PC はもちろん、2021 年 6 月時点で世界最速のスパコン「富岳」を使ってもなお、計算に莫大な時間がかかってしまいます。

このような場面では、動的計画法などの効率的なアルゴリズムを適用する必要があります。これらについては、本連載の第4回以降で紹介する予定です。

※1: この方法だと誕生月が12月の場合に12回の質問が必要ですが、実は4回以内で確実に当てる方法があります。これについては、今後の連載で取り上げる予定です。

※2: 「事象 A の起こり方が n 通り、事象 B の起こり方が m 通りある場合、事象 A・B の起こり方の組み合せは nm 通りある」という積の法則を使うと、N2 通りであることが分かります。