TCO12 2A 300pt : SwitchesAndLamps

問題概要

サイズN(<50)の置換σがある。いくつかの[1..N]の部分集合Sとσ(S)が与えられる。あなたは任意に集合Sを選んでσ(S)を得ることができる。σを確定させるためには最小でいくつの追加実験をする必要があるか判定するか求める問題。これまでの結果に矛盾がある場合は指摘する。

解法

既に得られた結果の内、互いにまったく区別できないような番号をまとめて、その最大サイズのみに応じて答えは決まる。分割してパラレルに処理することができるので最大サイズのlog程度が答えとなる。矛盾のチェックは集合Sとσ(S)のサイズが一致しているかどうか見てやれば良い。

acceptされたコード

色々余計なのがついていて汚い。

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

typedef long long int64;
const int MAX_N = 50;

int64 ss[MAX_N], ls[MAX_N];
int parent[MAX_N];
int dp[MAX_N + 1];

struct SwitchesAndLamps {

	int theMin(vector <string> switches, vector <string> lamps) {
		memset(parent, -1, sizeof(parent));
		const int K = switches.size();
		const int N = switches[0].length();
		const int64 MASK = (1LL<<N)-1;
		for(int i=2; i<=N; ++i){
			dp[i] = max(dp[i/2], dp[i-i/2]) + 1;
		}

		for(int i=0; i<K; ++i){
			for(int j=0; j<N; ++j){
				if(switches[i][j] == 'Y'){
					ss[i] |= 1LL<<j;
				}
				if(lamps[i][j] == 'Y'){
					ls[i] |= 1LL<<j;
				}
			}
			if(__builtin_popcountll(ss[i]) != __builtin_popcountll(ls[i])){
				return -1;
			}
		}

		int ans = 0;
		for(int i=0; i<N; ++i)if(parent[i] == -1){
			int64 s = MASK, l = MASK;
			for(int j=0; j<K; ++j){
				if(switches[j][i] == 'Y'){
					s &= ss[j];
					l &= ls[j];
				}
				else{
					s &= MASK & (~ss[j]);
					l &= MASK & (~ls[j]);
				}
			}
			if(__builtin_popcountll(s) != __builtin_popcountll(l)){
				return -1;
			}
			int cnt = 0;
			for(int j=0; j<N; ++j)if( (s>>j)&1 ){
				++cnt;
			}
			ans = max(ans, dp[cnt]);
		}

		return ans;
	}

};