Codeforces #253 Div1 A. Borya and Hanabi

CF253に参加。
ABしか解けなかったが、CDの難易度が高く正答者が少なかったため、ABのみで結構レートが回復。
http://codeforces.com/contest/442/problem/A

問題

5色×5種類の数字の計25種類のカードがある。
このうち自分が保持しているカードの一覧が与えられる。
ただし、自分はどのカードがどの色・数字かわからない。
そこで1回質問することで、特定の色または数字のカードの所在を全て知ることができる。

全てのカードの内容を把握するまでに必要な最小質問回数を求めよ。

解法

ある異なる2枚のカードを特定するには、両カードの色のうち片方または両方を質問済みであり、かつ両カードの数値のうち片方または両方を質問済みであることである。
どちらかでも満たさない場合、両カードのどちらがどちらか判断できない。

後は、5色・5数値の計10個の質問をbitmaskで総当たりし、全カードを判断できるかチェックして、判断できる最小bit数のものを答えればよい。

int N;
string D[101];
int num[5][5];

void solve() {
	int f,i,j,k,l,x,y,x2,y2;
	
	cin>>N;
	int mask=0;
	FOR(i,N) {
		string s;
		cin>>s;
		x=0;
		if(s[0]=='G') x=1;
		if(s[0]=='B') x=2;
		if(s[0]=='Y') x=3;
		if(s[0]=='W') x=4;
		num[x][s[1]-'1']++;
	}
	int ma=100;
	FOR(i,1<<10) if(ma>__builtin_popcount(i)) {
		int ng=0;
		FOR(y,5) FOR(x,5) FOR(y2,5) FOR(x2,5) {
			if(y==y2 && x==x2) continue;
			if(num[y][x]==0 || num[y2][x2]==0) continue;
			if(y!=y2 && (i&((1<<(y+5))|(1<<(y2+5))))) continue;
			if(x!=x2 && (i&((1<<(x))|(1<<(x2))))) continue;
			ng=1;
		}
		if(ng) continue;
		ma=__builtin_popcount(i);
	}
	cout<<ma<<endl;
}

まとめ

ちょっとややこしいけど、たまにはこういう問題もいいね。