全探索と計算量の見積もり

この記事の内容

可能性をすべて試すプログラム（全探索）と計算量の見積もりについて書きます。

問題の大きさの把握

数値の表現

通常C++では、整数はint型の変数で表現します。int型では、2³¹ ~ 2*10⁹ くらいまでの数を表現できるので、それより大きな数を扱うときは、long long 型を使用します。（2¹⁰ = 1024 ~ 10³を覚えておくとよいでしょう。）

符号付き整数の表現

type	bits	下限	上限	備考
int	32	-2³¹	2³¹ - 1	約20億
long	32/64			非推奨
long long	64	-2⁶³	2⁶³ -1	C++から標準形
_int128_t	128			gcc拡張

各型で表現可能な範囲は環境によって異なりうります。

時間と空間の制約

競技プログラミングで出題される各問題には、実行時間と利用可能メモリについての制約も付加されています。
プログラムの実行時間やメモリの使用量は、(1)実行環境、(2)問題の大きさ、(3)アルゴリズムによって大きく変わりうります。

(1)の実行環境については、通常競技プログラミング側の実行環境は、十分高速なので、手元で効率的に動くことが確認できたら大丈夫です。また(2)の問題の大きさについても、問題になることはほとんどないです。競技プログラミングにおいては（あるいは普通のプログラミングにおいても）、(3)のアルゴリズムについてがどのような役割を果たすかが、最も重要な話題です。

組み合わせを試す

コンピュータが得意な解法はすべての組み合わせを力づくで試すことです。実際多くの問題はそれで解くことができます。全ての可能性を試すためには、for文を用いたり、再帰を用いたりします。

計算量の簡単な検討

for文が最大何回回るかを考えることで、計算量を見積もることができます。C++で大体1秒間のどれくらいの計算ができるかは、下の表の通りなので、問題を解くときの目安にしてください。

演算回数	コメント
1 000 000	余裕をもって実行可能
10 000 000	多分可能
100 000 000	とてもシンプルな演算なら可能

この表の数値は実行環境によって変わりますが、最近の多くのコンピュータのCPUは、1GHz(10⁹)程度で動作しているので、CPUが100サイクル以内にできる演算なら、1秒間に10⁷回程度まではおそらく実行可能と期待できます。
演算によってサイクル数は異なり、たとえば、メモリ参照やnew/deleteは、単純な算術演算よりそれぞれ10倍,100倍程度遅いです。

試行回数の見積もりと計算の手順の改良

下の例題を参考にして、計算方法の微調整により、計算量が異なることを見ていきます。

例題：Space Coconut Crab
宇宙ヤシガニの出現場所を探す．エネルギー E が観測されたとして，出現場所の候補は，x + y² + z³ = E を満たす整数座標 (x, y, z) で，さらに x + y + z の値が最小の場所に限られるという．x + y + z の最小値を求めよ．(x, y, z は非負の整数，E は正の整数で 1, 000, 000 以下，宇宙ヤシガニは，宇宙最大とされる甲殻類であり，成長後の体長は 400 メートル以上，足を広げれば 1, 000 メートル以上 ← 同じ数値でも重要な制約と余計な情報の区別に注意)
（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2012 より）

まず次のような方針を考える。

方針１：変数x,y,zのすべてのパターンを調べ、それが条件を満たすかどうかを調べる。
この場合どれくらいの計算量が必要かを見積もってみましょう。x,y,zの動く範囲は、それぞれ、x:[0,E],y:[0,E^{1/2}],z:[0,E^{1/3}]です。Eの最大値が10⁶ より、最大で $10 ^ 6 * 10 ^ 3 * 10 ^ 2 = 10 ^ {11}$ の計算量が必要です。これは、制限時間の8秒以内には終わりそうにありません。

したがって別の方針を考える必要があります。

方針２：xとyのみを考え、 $E - x - y ^ 2 = z ^ 3$ からzを決定する。この場合は、(x, y)の組のみを考えれば良いので、計算量のオーダーは、 $10 ^ 6 * 10 ^ 3 = 10 ^ 9$ で済みます。
方針３：上の方針２で動かす変数をx,zにする。この場合は、計算量のオーダーは、 $10 ^ 6 * 10 ^ 2 = 10 ^ 8$ となり、方針2よりも計算量を減らせています。
方針４：方針２で動かす変数をy,zにする。この場合は、計算量のオーダーは、 $10 ^ 3 * 10 ^ 2 = 10 ^ 5$ となり、方針3よりもさらに計算量を減らせています。