POJ-2345, Times-1042 : Central heating

問題概要

盤面サイズ250のライツアウトを解いて最短かつ辞書順最小の解を出現する。

解法

連立一次方程式。最短かつ辞書順最小が難しいが、問題文をよく読むとランク落ちしないと書いてあるので最小も何もなく解は一意に定まる。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int calcEquationSystemMod2(vector<BitSet> &Ab, BitSet& x) {
	const int n = Ab.size(), m = Ab[0].size - 1;
	x.init(m);
	bool uniq = true;
	int val = 0;
	for (int i = 0; i < n; ++i) {
		if (val == m) {
			for (int j = i; j < n; ++j) {
				if (Ab[j][val]) {
					return 0;
				}
			}
			break;
		}
		int foundOne = -1;
		for (int j = i; j < n; ++j) {
			if (Ab[j][val]) {
				foundOne = j;
				break;
			}
		}
		if (foundOne >= 0) {
			swap(Ab[i], Ab[foundOne]);
			for (int j = i + 1; j < n; ++j) {
				if (Ab[j][val]) {
					Ab[j] ^= Ab[i];
				}
			}
		}
		else {
			uniq = false;
			for (int j = 0; j < i; ++j) {
				Ab[j].turnOff(val);
			}
			--i;
		}
		++val;
	}
	val = m - 1;
	int i = n - 1;
	for (;i >= 0 && Ab[i].countPopulation() == 0; --i) ;
	for (;i >= 0 && val >= 0; --val) {
		if (Ab[i][val]) {
			if (Ab[i][m]) {
				x.turnOn(val);
				for (int j = 0; j < i; ++j) if (Ab[j][val]) {
					Ab[j].turnOff(val);
					Ab[j].flip(m);
				}
			}
			else {
				for (int j = 0; j < i; ++j) {
					Ab[j].turnOff(val);
				}
			}
			--i;
		}
	}

	return uniq ? 1 : -1;
}

void solve() {
	int N; scanf("%d", &N);
	vector<BitSet> matrix(N);
	for (int i = 0; i < N; ++i) {
		matrix[i].init(N + 1);
	}
	for (int i = 0; i < N; ++i) {
		int x;
		for (;scanf("%d", &x), x!=-1;) {
			matrix[x-1].turnOn(i);
		}
		matrix[i].turnOn(N);
	}

	BitSet x;
	calcEquationSystemMod2(matrix, x);
	vector<int> ans;
	for (int i = 0; i < N; ++i) if (x[i]) {
		ans.push_back(i + 1);
	}
	for (int i = 0; i < int(ans.size()); ++i) {
		printf("%d%c", ans[i], i==int(ans.size())-1 ? '\n' : ' ');
	}
}

int main() {
	solve();

	return 0;