はじめに

前回の連載では、AtCoderで問題を解くための考え方の基本となる全探索について解説しました。
しかし全探索はあくまで基本のテクニックであり、それだけでは難しい問題を解くことはできません。

そこで今回は、実行時間が間に合わないような難しい問題を解くために一体どのようなテクニックがあるのかについて説明していこうかと思います。

計算を速くするテクニック

計算を速くするテクニックはたくさんありますが、よく使うものはそこまで多くありません。

極めて多いのは、以下のようなテクニックです。

1) 同じ計算を2回行わないようにする。
2) 必要のない計算を行わないようにする。
3) 算数/数学的な考え方によって、探索を省略する。
4) 答えの範囲を効率よく狭めていくことで、探索回数を減らす。

このうち、今回最も覚えてもらいたいものは、1番目や2番目です。書いてあることは極めて当たり前のことに見えるかもしれませんが、実は気づかないうちにこうした無駄な計算をしてしまうことはものすごく多いです。

3番目の算数/数学的知識は高校まで習ったものでほとんどの場合は問題がないですし、4番目のパターンは、二分探索などで出てくるものですが、1・2番目と比べるとそこまで頻出というわけではないので、この1番目、2番目の考え方が競技プログラミングにおいて最も肝となる考え方であるといっても過言ではありません。

さて、それでは、実際に問題を解いてみることで、こうしたテクニックの重要性を体感してみましょう。

問題

制約

入力

入力例

出力例

(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,1,6),
(1,2),(1,3),(1,4),(1,5),(1,6),
(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),
(3),(4),(5),(6)

の 21 通りが答えになります。

解説１

コンテストだと少しひねった問題が出題されがちなので、今回は超典型的なオリジナル問題を作成してみました。AtCoder以外ではすでに出題されている問題だと思います。

問題概要について簡単に言うと、Nマスのすごろくでゴールするまでのサイコロの出目のパターンは何通りありますか、という問題です。

答えを「10億7で割った余りを求める」というのは不思議に思うかもしれませんが、これは競技プログラミングでは非常によくある形式で、実は実用性のある求め方です。

10億7は素数であり、ほかの素数でも同様に計算をすると「中国の剰余定理」という定理を使って、組み合わせが何通りあるかを正確に求めることができるようになります。こうした計算をすることにより、途中計算で多倍長整数を使わなくても良くなるわけです（少し難しい話ですので、よくわからない場合は読み飛ばしていただいてかまいません）。

さて、それでは、解き方に戻りましょう。

まず、考え方の基本は全探索です。どのようにすれば全探索できるでしょうか？前回と同じように、再帰関数を使って深さ優先探索を書いてあげれば、全探索をすることが可能です。

図にすると、こんな感じの探索木を書くことができます。

さて、それでは実際にコードを書いてみましょう。

想定誤解法

#include <iostream>
#include <vector>
using namespace std;

int N;

// 残りAマスの時に、ゴールまでの出目が何通りあるか求める
int dfs(int A) {
	if (A <= 0) return 1;
	
	int ans = 0;
	// 1から6までの全通りについて調べる
	for (int i = 1; i <= 6; i++)
	{
		ans += dfs(A - i);
		ans %= 1000000007; // 求めるのは10億7で割った余り
	}

	return ans;
}

int main() {
	// 入力を受け取る
	cin >> N;

	// 深さ優先探索で答えを求め、出力する
	cout << dfs(N) << endl;
}

解説２

さて、全探索が書けましたが、今回の問題では、Nの制約が10万まであり、組み合わせが非常に多くなります。これでは、実行時間が極めて長くなってしまいます。どれくらい長くなってしまうでしょうか？　何分？何時間？

いえ、実は地球が爆発するくらいまで待っても、N=100,000の最大ケースでは実行を終えることができません。非常に高速化しなければならない問題です。

しかし、あることに気づけば、答えを高速に求めることは非常に簡単になります。

それは、「同じ計算を2回以上している」という無駄がある、という点です。先ほど列挙した図では、すべてが別の経路を表しているので一見無駄な計算なんてないようにも思えます。ですが実は、大量の無駄が発生してしまっているのです。

画像の2つの赤丸に注目してみましょう。

(1,1)という目が出た後の探索は「2マス進んだ後に、ゴールまでの出目が何パターンあるか」を調べています。

(2)という目が出た後の探索も「2マス進んだ後に、ゴールまでの出目が何パターンあるか」を調べています。

さて、この2つを比べてみると当然同じ探索結果が出てきます。両方とも同じものを求めているのです。

ということで、実は先ほどの全探索では、同じ計算が何度も発生してしまっていました。これを再計算しないようにしてあげるだけで、極めて速く処理をすることができます。

この実装方法は、実は非常に簡単です。その計算が既に行われているのであれば、その結果を即座に返すように関数を書き直してあげれば良いのです。

こうするとcalc関数の中身が実行される回数はN回程度となるため、計算が非常に高速に終わるようになります。こうした同じ計算を2回しないように処理をまとめたり結果をメモしておくテクニックを動的計画法と呼び、今回のような再帰中にメモするテクニックを特に競プロ界隈ではメモ化再帰と呼びます。

この問題を機に、ぜひ覚えてください。

解答

#include <iostream>
#include <vector>
using namespace std;

int N;
vector <int> dp;

//残りAマスの時に、ゴールまでの出目が何通りあるか求める
int dfs(int A) {
	if (A <= 0) return 1;
	// もし計算済みであれば、答えをそのまま返す
	if (dp[A] >= 0) return dp[A];

	int ans = 0;
	// 1から6までの全通りについて調べる
	for (int i = 1; i <= 6; i++)
	{
		ans += dfs(A - i);
		ans %= 1000000007; //求めるのは10億7で割った余り
	}

	// 答えを返す前に、結果をdp配列にメモする
	return dp[A] = ans;
}

int main() {
	// 入力を受け取る
	cin >> N;
	// 答えをメモするdp配列の初期化。-1の時未計算
	dp = vector<int>	(N + 1, -1);
	// 深さ優先探索で答えを求め、出力する
	cout << dfs(N) << endl;
}

おわりに

今回は動的計画法というテクニックを紹介しました。これはプログラミングコンテストでもそれ以外でも、非常によく出てくるテクニックです。

特に今回のような使い方は、プログラミングコンテスト以外の場面でも非常によく使います。動的計画法、というとピンと来ないかもしれませんが「計算結果をキャッシュする」と言えばプログラマであればピンとくるのではないでしょうか？

キャッシュ、と単純に言ってしまうと、ただ最終的に求める結果のみを記憶しておくもの、みたいにイメージしてしまう人が多いかもしれませんが、競技プログラミングでは途中計算の結果をキャッシュすることで、全体を高速化する、というような多種多様なキャッシュの使い方が出てきます。

この考え方は実用的な部分でも非常に役に立つところであり、また競技プログラミング以外で身に着けることはなかなか難しいテクニックでもあります。

競技プログラミングの最大のポイントである動的計画法、みなさんぜひマスターしてみてください！

さいごに

連載「AtCoderではじめる競技プログラミング」は、今回で終了になります。まだたくさんのテクニックが残っていますが、ここまでの内容を理解すれば競技プログラミングの世界に入っていくこと自体は、まったく問題なくできるかと思います。

続きはぜひ皆さんがコンテストに出場して、コンテストの問題の中で身に着けていっていただければと考えています。

皆様がAtCoderに参加してくれることを楽しみにしています！