TopCoder初心者向け総当たり特集 - じじいのプログラミング

この日記は、tanzakuさん主催のCompetitive Programming Advent Calendar - PARTAKEの記事です。普段、TopCoderのニコニコ生放送（http://com.nicovideo.jp/community/co78570)をしているのですが、最近は簡単な問題をじっくり解説するということが減ってきたので、今回は基本的な総当たりを取り上げてみることにします。これがちゃんとできれば、TopCoderのDivision 2はすぐに脱出できると思います。TopCoder以外の一般のプログラムでも、総当たりは使うことがあると思いますし、ぜひ使いこなせるようになりましょう。

forループを使った総当たり

問題1 FizzBuzzを数える
A以上B以下の整数で、3か5で割り切れるものは、何個ありますか？

入力・制約条件
int A: Aは、0≦A≦1000000を満たす整数
int B: Bは、A≦B≦1000000を満たす整数

例1
入力:A=5,B=10
出力:4
5,10が5で割り切れ、6,9が3で割り切れます。つまり、5,6,9,10の4つ。

例2
入力:A=14,B=16
出力:1
15は3でも5でも割りきれます。2重にカウントしないように注意です。

「もしかしたら数式１個だけで答えが求められる？かぶって数えないようにするには、 3と5の公倍数は15だから、うーん…」
と悩んだ人も多いかもしれません。その読みは正しいのですが、もっと楽をすることができます。制約条件に注目すると、A,Bともに100万までなので、forループで総当たりすることができます。

int problem1(int A,int B)
{
	int result = 0;
	for (int i = A; i <= B; i++) // i<B と間違う人は意外と多いです。チャレンジフェーズの狙いめです。
	{
		if(i%3==0 || i%5==0) // 割り切れるの判定には、"余り=0"を使います。
		{
			result++;
		}
	}
	printf("%d\n",result);
	return result;
}

TopCoderの問題の場合は、TopCoderのコンピューターで2秒以内に実行が終わらないと、不正解となってしまいます(TLE:Time Limit Exceededと呼んでます）。forループの中身にもよりますが、1000万回のループなら余裕、1億回のループならまぁなんとか間に合うというかんじです。

プログラムを書く前に制約条件をみて、forループで総当たりができないか判断しましょう。
プログラムを書いた後は、必ずテストをしましょう。この問題なら、Aに小さい値、Bに大きい値が入るケースがもっとも時間がかかるので、A=0,B=1000000を入力して、TLEしないかをチェックしましょう。

多重のforループを使った総当たり

問題2 FizzBuzzを数える(2)
xは0以上X以下の整数、yは0以上Y以下の整数、zは0以上Z以下の整数とします。
x+y*y+z*z*z*zが3か5で割り切れる、(x,y,z)の組み合わせは、何通りありますか？

入力・制約条件
int X: Xは、0≦X≦100を満たす整数
int Y: Yは、0≦Y≦100を満たす整数
int Z: Zは、0≦Z≦100を満たす整数

例1
入力:X=100,Y=100,Z=100
出力:481408

変数が3つに増えましたが、このような場合はforループを多重にすることで、(x,y,z)のすべての組み合わせを試すことができます。forループのループ回数は、X,Y,Zの最大が100なので、100*100*100で100万回程度。余裕で2秒以内に実行できます。

int problem2(int X,int Y,int Z)
{
	int result = 0;
	for (int x = 0; x <= X; x++)
	{
		for (int y = 0; y <= Y; y++)
		{
			for (int z = 0; z <= Z; z++)
			{
				// オーバーフローにはくれぐれも注意しましょう。
				// tmpは100*100*100*100=1億程度はいきますが、
				// intは21億ぐらいまで取れるので、オーバーフローしません。
				const int tmp = x + y*y + z*z*z*z;
				if(tmp%3==0 || tmp%5==0)
				{
					result++;
				}
			}
		}
	}
	printf("%d\n",result);
	return result;
}

ビットを使った総当たり

問題3 絵の具選び

7色（赤、橙、黄、緑、青、藍、紫）の絵の具があります。そのうち3色を選んで、絵を描くことにしました。
絵の具の選び方は何通りありますか？

高校数学で、組み合わせを習えば、Combination(7,3)=(7*6*5)/(3*2*1)=35通りと簡単に出せますが、忘れている人も多いかと思います。さて、この問題は総当たりなら、どう解くと良いでしょう？
まず、問題2と同じように、forループで書くと以下のように7重のループになります。

int problem3nagai()
{
	int result = 0;
	for (int aka = 0; aka <= 1; aka++) // =0 その色を選ばない, =1 選ぶ
	{
		for (int daidai = 0; daidai <= 1; daidai++)
		{
			for (int ki = 0; ki <= 1; ki++)
			{
				for (int midori = 0; midori <= 1; midori++)
				{
					for (int ao = 0; ao <= 1; ao++)
					{
						for (int ai = 0; ai <= 1; ai++)
						{
							for (int murasaki = 0; murasaki <= 1; murasaki++)
							{
								const int num_colors = aka+daidai+ki+midori+ao+ai+murasaki;
								if(num_colors==3)
								{
									result++;
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%d\n",result);
	return result;
}

もし解答が思い浮かばなかったら、この解答でも問題ないのですが、この解答では、

コード量が多いので、書き間違う可能性が増える。
このコードでは7色にしか対応できない。「N色」のように色数が変数で与えられたら、対応できない。

という欠点があります。
こういう場合は、以下のように、ビットを使ったforループで書くと良いでしょう。

int problem3()
{
	// MAX_COLORS=20ぐらいまでなら、
	// forループは2^20*20=20971520回なので、2秒以内に間に合うと思います。
	const int MAX_COLORS = 7;
	int result = 0;
	for (int all = 0; all < (1<<MAX_COLORS); all++)
	{
		int num_colors = 0;
		for (int color = 0; color < MAX_COLORS; color++)
		{
			if( all & (1<<color) )
			{
				num_colors++;
			}
		}
		if(num_colors==3)
		{
			result++;
		}
	}
	printf("%d\n",result);
	return result;
}

意味的には、先ほどのforの多重ループのコードと全く一緒です。2進数とビットについてはわからないと以下の説明が分からないかもしれません。各自勉強しましょう。
まず、最初のforループで全ての色パターンを列挙します。allに色パターンが入ります。allは最大で2のMAX_COLORS乗つまり(1＜＜MAX_COLORS)と書くことができます。

次のforループでは、あるallについて、何色使っているかを求めます。変数colorがそれぞれの色に対応しています。1＜＜colorで、ある色を表すことができます。colorをループさせることで、1色ずつ調べていきます。もし、all & (1＜＜color)なら、その色が使用されているということなので、num_colorsを1ずつ足していきます。最終的には、allの色パターンで使用されている色数が、num_colorsに入ります。これが3になるかどうかをチェックすれば良いです。

ちなみに、この問題は深さ優先探索や、動的計画法など、いろいろな解法がありますので、ぜひ考えてみてください。また、ビットのチェック方法、ビットの数え方も、いろいろなやり方があるので、考えたり他の人のコードを読んだりしましょう。

ビットを使った総当たり（応用）

問題4 0-1ナップサック問題
品物がN種類（重量weight[i]、価値 value[i]、0≦i＜N）があります。
ナップサックには、合計で重量Wまで、品物をつめることができます。
それぞれの品物は最大で1つだけしか選べません。
あなたは、詰める品物の価値の合計が最大になるように、ナップサックに品物を詰めたいです。
そのときの価値の合計を最大値はいくらでしょう？

入力・制約条件

int N: Nは、1≦N≦20を満たす整数
int W: Wは、0≦N≦10000000を満たす整数
vector  weight: weightの要素数はN個。1≦weight[i]≦10000000 を満たす整数
vector  value:  valueの要素数はN個、 1≦value[i] ≦10000000  を満たす整数

例1
入力:N=5,W=10,weight={1,2,3,4,3} value={2,5,10,2,6}
出力:23
0番目・1番目・2番目・4番目のを詰めると、重量1+2+4+3=10、価値2+5+10+6=23でベストです。

一気に難問がでてきたように見えます。「ナップサック問題」と聞いて、wikipedia(http://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)を読んで
「NP完全だし、これは無理orz」
とか、最強最速アルゴリズマーの解説を読んで(http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html)
「動的計画法、分からん」
とか、びびらないようにしましょう。
以上の解説は、もちろん正しいですが、この問題ではNが20と少ないです。2^20=1048576。これにループの分をかけても1048576*20=20971520と1億以下。これなら、総当たりをすることができます。

int problem4(int N, int W, vector <int> weight, vector <int> value)
{
	int max_value = -1;
	for (int all = 0; all < (1<<N); all++)
	{
		int sum_weight = 0;
		int sum_value = 0;
		for (int i = 0; i < N; i++)
		{
			if (all>>i & 1) // ビットのチェックの別方法。
			{
				sum_weight += weight[i];
				sum_value  += value[i];
			}
		}
		if(sum_weight<=W)
		{
			max_value = max(max_value,sum_value);
		}
	}

	printf("%d\n",max_value);
	return max_value;
}