YUHA C88 謎解きコン : C - 酒場の冒険者たち

似た問題考えてたけど出てしまったか。
http://yuha-c88.contest.atcoder.jp/tasks/yuha_c88_c

問題

N人の冒険者の名前が与えられる。
それぞれの冒険者は正直者か嘘つきである。
また、各冒険者が１人１個ずつ「誰々は正直/嘘つきである」という意見を発言する。

全体として発言に矛盾のない正直者/嘘つきの分類が可能ならそれを答えよ。

解法

N≦20なので、2^N通り正直者/嘘つきの総当たりをすればよい。

int N;
string S2[21];
pair<string,int> S[21];
int T[21];
int good[21];
int rev[21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i].first;
		S[i].second=i;
	}
	sort(S,S+N);
	FOR(i,N) {
		S2[i]=S[i].first;
		rev[S[i].second]=i;
	}
	
	FOR(i,N) {
		cin>>s;
		FOR(x,N) if(s==S2[x]) T[rev[i]]=x;
		cin>>s;
		cin>>s;
		cin>>s;
		good[rev[i]]=s[0]=='g';
		cin>>s;
	}
	int best=-1;
	
	for(int mask=0;mask<1<<N;mask++) {
		int ng=0;
		
		FOR(i,N) {
			if(mask&(1<<i)) {
				if(good[i]) {
					if((mask&(1<<T[i]))==0) ng++;
				}
				else {
					if((mask&(1<<T[i]))!=0) ng++;
				}
			}
			else {
				if(good[i]==0) {
					if((mask&(1<<T[i]))==0) ng++;
				}
				else {
					if((mask&(1<<T[i]))!=0) ng++;
				}
			}
		}
		if(ng) continue;
		
		if(best==-1 || __builtin_popcount(mask)>__builtin_popcount(best)) best=mask;
	}
	if(best==-1) {
		cout<<"No answers"<<endl;
	}
	else {
		FOR(i,N) if(best&(1<<i)) cout<<S2[i]<<endl;;
	}
}

まとめ

全員嘘つきな冒険者の場合、みんな「誰々さんは正直者です」って答えるのか。
こんな酒場で冒険者を募りたくないな…。