ABC015 C問題（高橋くんのバグ探し）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）015 C問題をC++で解いてみました。ABC015は、2014年11月22日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 高橋くんのバグ探し（Difficulty : 912（参考値））

問題の詳細は、リンク先をご覧ください。

ABC015 C問題 高橋くんのバグ探し

多重ループを再帰関数で実装する典型問題です。AtCoder Problems による Difficulty は 912（参考値）でした。

解答案

C++ プログラム例（ABC015C）

1重ループになることもあり、最大で5重ループとなることがあります。回数が不定な多重ループは再帰関数で実装ができます。

以下は、再帰関数 dfs の補足です（16ー26行目）。

• 全体はラムダ式で実装しました。
• ループした回数（$i$）とそれまでの排他的論理和（$v$）を引数に持ちます。
• $n$ 回ループした場合、排他的論理和が0になっていれば、bool変数 result を true に設定します。
• ループの各要素（$k$ 個）に対して再帰関数を呼び出し、次のループを実行します（24行目）。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<vector<int>> t(n, vector<int>(k));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < k; ++j) {
			cin >> t[i][j];
		}
	}

	bool result = false;
	auto dfs = [&](auto self, int i, int v) -> void {
		if (i == n) {
			if (v == 0) {
				result = true;
			}
			return;
		}
		for (int j = 0; j < k; ++j) {
			self(self, i + 1, v ^ t[i][j]);
		}
	};
	dfs(dfs, 0, 0);

	if (result) {
		cout << "Found" << endl;
	} else {
		cout << "Nothing" << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

使いこなすのは難しいですが、再帰は強力なツールだと考えています。

引き続き ABC の問題を紹介していきます。