計算量も知らなかったエンジニアが解説する全探索アルゴリズム入門

こんにちは！@bluesky177896です。
以前の記事で紹介した通り、自分は競技プログラミングを提供するサイトの一つである、AtCorderに登録しています。
そこで頻出するアルゴリズムの一つである、「全探索」について今回はまとめてみました。
賢い方はすぐピンと来ると思いますが、自分のような「計算量？なんだそいつうめぇのか？」という人間は最初知らなくて大変だったので、
分かりやすく解説していきます。

全探索とは

全探索という漢字で察した人もいるかと思いますが、「全てのパターンを探索してみる」アルゴリズムとなります。
Wikipediaでは「力任せ探索」という項目名になっています。

例えば、以下のような設問があったとします。

こうなったとき、色々考え方はあると思います。
全探索で考えるとどうなるかというと、以下のようなグラフを作って埋めていくようなイメージになります。

これを手動で作ろうと思ったら地獄でしかありませんが、
私たちがやるのは競技プログラミング！
実際にコードに落としこんで考えていきましょう。

コードに落とし込むときは、単純に考えてしまって良くて、
forを使って各貨幣の枚数制限回数分処理を行い、貨幣の種類分forのネストを深くすればOKです。

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		// 各貨幣の制限枚数
		int yen500 = 300;
		int yen100 = 200;
		int yen50 = 100;

		// ちょうどにしたい金額
		int just = 15000;

		// マッチしたパターン数
		int count = 0;
		
		// 500円玉
		for (int i = 0; i < yen500; i++) {
			// 100円玉
			for (int j = 0; j < yen100; j++) {
				// 50円玉
				for (int k = 0; k < yen50; k++) {
					// 枚数×各金額がちょうどの金額と一致したらマッチしたパターン数を増やす
					if (i * 500 + j * 100 + k * 50 == just) {
						count++;
					}
				}
			}
		}

		System.out.println(count);
	}
}

この通り、比較的短いコードで簡単にかけてしまいました。

ちなみに、競技プログラミングには「Time Limit Exceeded (TLE)」という判定があります。
これは、英語の通り「時間切れ」で、あまり処理が長いと答えがあっていても回答を受け付けてもらえません。
全探索にはこのTLEの危険が常に付きまとっていて、
目安としては、int型をforで処理する回数が10^12程度にならなければ問題ないかと思います。
(AtCorderで言うと、～一部のC問題までなら全探索でTLEが出ることはまずないと思います。
また、C++などはもう少し無理できるかもしれません。)

ちょこっと応用

上記の問題は、非常に単純なループで作成しました。
ただ、下の方に書いたように、全探索は制限等によっては処理時間が非常に長くなるという欠点があります。
なので、ちょっとした応用をして時間を短縮出来るようになると嬉しいし、C問題以降を解いていくための練習にもなります。

例えば上の例でみていくと、実は最後の50円のループは回す必要がありません。
というのも、500円玉、100円玉の枚数が決定した時点で、
ちょうどにしたい金額にするために必要な50円玉の枚数を私たちは簡単に求めることが出来るからです。
例えば、ループの途中で500円玉が10枚、100円玉が10枚のパターンが来るとします。
この時点で7000円で、残り必要な金額は8000円になります。では、必要な50円玉の枚数は？
8000/50で160枚です。
50で割り切れて、かつ制限枚数以内に収まっています。
これより上にもこれより下の枚数にもできないので、
この時点で50円玉の他の枚数で合計がどうなるかは計算する必要はありません。
なので、この時点でマッチしたパターン数を一つ増やして、次のループ処理に移ってOKとなります。

これをコードに落とし込むと、以下の様になります。

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		// 各貨幣の制限枚数
		int yen500 = 300;
		int yen100 = 200;
		int yen50 = 100;

		// ちょうどにしたい金額
		int just = 15000;

		// マッチしたパターン数
		int count = 0;

		// 500円玉
		for (int i = 0; i < yen500; i++) {
			// 100円玉
			for (int j = 0; j < yen100; j++) {
				// 判定用にちょうどの金額-500円100円の総金額を引いた数を出しておく
				int tmpMoney = just - (500 * i + 100 * j);
				if (tmpMoney >= 0 && tmpMoney % 50 == 0 && tmpMoney / 50 < yen50) {
					count++;
				}
			}
		}

		System.out.println(count);
	}
}

tmpMoneyを0以上に限定していますが、これは制限枚数がある数を超えると、
丁度の金額から引いた時にマイナスになり、計算がおかしくなるからです。

この他にも、様々な方法で回答をより高速に出せるようにしている方が沢山います。
あまり上位すぎると、今度は読むのが難しくて参考に出来ませんが、
自分より少し上くらいのレート帯の方のコードを参考にするなどして色々な工夫を覚えていったり、
自分で見つけられるようになるととても楽しいです。

上で参考にしたAtCorderの問題の次の問題の「C – Candies」も、
普通に全探索をしてしまうとTLEする可能性がありますが、
「ちょっとした工夫」をすることで解くことが可能です。
(自分が初めて解説無しに解けたC問題で、恐らくそんなに難易度が高くないと思うので是非C難しい層の方はチャレンジしてみてください！)

まとめ

というわけで、文系でも理系でもない人間が全探索についてまとめてみました。
多分色々粗はありますが、究極的には「AC」が出ればいいのです。
このくらいのふんわりした理解でも全探索問題ならCでもコンスタントにACを出せるので、全探索を知らない方の参考や励みになればと思います。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
競技プログラミング界隈では有名な本で、
必要なアルゴリズムやテクニックが分かりやすく解説されている本です。
書かれている言語は「C++」なので、馴染みのない方にはやや解読が難しいかもしれませんが、
少なくともJavaユーザーの私はなんとか解読出来るレベルなので、かなり読みやすく書かれています。
(もしくは、これを機にC++デビューをしても良いかもしれません。
少なくともJavaと違って記述量が短く済むので、コードを書く時間で圧倒的に有利だと思います。)