まとめた経緯

「競技プログラミングの鉄則」という本で全探索を勉強している時に、効率的な全探索の方法があるよ！と紹介されていたビット全探索。

Atcoder公式のC++教材にも解説が載っているが、自分の手で実装してみないと理解できないと悟ったので問題を解いていきました。

今回はその備忘録としてqiitaに残しておこうと思ったのが記事執筆に至った経緯です。

問題解いていくよ

ABC014 - B - 価格の合計

ビット演算の基礎が理解できているか確かめられる問題。導入として最適だった。

問題としては、ある値段付きの買い物リストから、購入するかどうかを01の羅列で入力されるので、合計額を計算しろというもの。

実際に実装したコードを添付しておく。

#include <iostream>

using namespace std;

int n, X;
int a[30];

int main()
{
	cin >> n >> X;
	for (int i = 0; i < n; i++) cin >> a[i];
	int price = 0;
	for (int i = n - 1 ; i >= 0; i--)
	{
		if (X / (1 << i) == 1)
		{
			price += a[i];
			X -= (1 << i);
		}
	}
	cout << price << endl;
	return 0;
}

ABC128 - C - Switches

N個のスイッチとM個の電球があり、スイッチと電球の繋がり方を入力でもらえるので、電球が全て光るスイッチの入れ方が何通りあるか調べる問題。

ビットをずらしながらそれぞれの電球が光っているかを一つずつ確認していった。

これも実装を下に添付しておく。

#include <iostream>

using namespace std;

int N, M;
int k[20];
int s[20][20];
int p[20];

int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> k[i];
		for (int j = 0; j < k[i]; j++)
		{
			cin >> s[i][j];
		}
	}
	for (int i = 0; i < M; i++) cin >> p[i];

	int count = 0;
	int flag = 1;
	for (int i = 0; i < (1 << N); i++)
	{
		flag = 1;
		for (int j = 0; j < M; j++)
		{
			int onswitch = 0;
			for (int l = 0; l < k[j]; l++)
			{
				if ((i >> (s[j][l] - 1)) & 1)
				{
					onswitch++;
				}
			}
			if (onswitch % 2 != p[j])
			{
				flag = -1;
				break;
			}
		}
		if (flag == 1)
		{
			count++;
		}
	}
	cout << count << endl;
}

ABC147 - C - HonestOrKind

デバックにてこずった問題。少し可読性低くて恐縮ですが、printfデバックの跡を意図的に残しています。

問題としては、「全て正しい証言をする人」と「てきとーに発言する人」が全員証言をした。このグループの中に「全て正しい証言をする人」がmax何人いても辻褄が合うか、という問題。

#include <iostream>

using namespace std;

int N;
int A[20];
int info[20][20][20];

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		for (int j = 0; j < A[i]; j++)
		{
			cin >> info[i][j][0] >> info[i][j][1];
		}
	}
	int max_person = 0;
	for (int i = 0; i < (1 << N); i++)
	{
		// int testimony[20] = {-1};
		int flag = 1;
		int count = 0;
		for (int j = N - 1; j >= 0; j--)
		{
			if ((i >> j) & 1)
			{
				// printf("i is [%d] j is [%d] max is[%d]\n", i , j, max_person);
				for (int k = 0; k < A[j]; k++)
				{
					int tmp_person = info[j][k][0] - 1;
					int tmp_num = info[j][k][1];
					// if (i == 3)
					// {
					// 	printf("j is [%d] k is[%d] person is [%d] tmp is[%d]\n",j, k, tmp_person , tmp_num);
					// }
					if (tmp_num == 0)
					{
						if (((i >> tmp_person) & 1))
						{
							flag = -1;
							break;
						}
					}
					if (tmp_num == 1)
					{
						if (!((i >> tmp_person) & 1))
						{
							flag = -1;
							break;
						}
					}
					// if (i == 3)
					// {
					// 	printf("j is [%d] person is [%d] tmp is[%d]flag is [%d]\n",j, tmp_person , tmp_num, flag);
					// }
					// if (testimony[tmp_person] == -1)
					// {
					// 	testimony[tmp_person] = tmp_num;
					// }
					// else if (testimony[tmp_person] != tmp_num)
					// {
					// 	flag = -1;
					// 	break;
					// }
				}
			}
			// if (i == 3)
			// {
			// 	printf("j is [%d] flag is [%d]\n",j, flag);
			// }
			if (flag == -1)
			{
				break;
			}
		}
		// printf("i is [%d]max is [%d] flag is[%d]\n",i, max_person, flag);
		if (flag == 1)
		{
			int bit_count = 0;
			int temp_i = i;
			while (temp_i != 0) {
				bit_count += temp_i & 1;
				temp_i >>= 1;
			}
			count = bit_count;

			if (max_person < count)
				max_person = count;
		}
	}
	cout << max_person << endl;
	return 0;
}

ABC061 - C - ManyFormula

0から9までの数字で成り立つ文字列が渡される。数字同士の間に+を入れたり入れなかったりして区切り、和を計算する。全ての入れ方のパターンの式の和を計算し、総和を出力せよ、という問題。

文字列を前からn文字目からm文字分だけ切り取る関数、substr(n, m)を調べれたのがキーだった。1問前に1時間くらいかかったのに対して、これは10分で解けた。

一つだけ落とし穴は、切り取った後の文字列をint型に変換するところでstoi関数を使用しようとしたところ、int型に収まらない数字もあると怒られたポイントだった。結局stoiのlong long型まで対応しているstoll関数を使用することで事なきを得た。

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string S;
	cin >> S;
	int len = (int)S.size();
	long long total = 0;
	for (int i = 0; i < (1 << len - 1); i++)
	{
		int front = 0;
		for (int j = 0; j < len - 1; j++)
		{
			if ((i >> j) & 1)
			{
				string sub_str = S.substr(front, j - front + 1);
				total += stoll(sub_str);
				front += j - front + 1;
			}
		}
		string sub_str = S.substr(front, len - front);
		total += stoll(sub_str);
	}
	cout << total << endl;
	return 0;
}

参考記事

今回といた問題の大半は@Jessica_nao_さんがすでにまとめて頂いていたものを解いてみた形になります。

わかりやすくまとめて頂いて感謝しかありません！