kmjp's blog

競技プログラミング参加記です

Codeforces #488 Div1 B. Open Communication

制限が小さいことでだいぶ戸惑った。
http://codeforces.com/contest/993/problem/B

問題

2人が1~9で構成された数字のペアを1つずつ保持しているとする。
ペアは異なる数字で構成されており、かつ2人が持つペアは同じ数字を1つだけ持つ。

1人目は2人目にN個の、2人目は1人目にM個のペアを伝えた。
いずれも、伝えた中に自身の保持するペアをどこかに含んでいる。

このやり取りを外部から見て、以下判断せよ。

  • 両者の保持するペアの共通数字が特定できればそれを答えよ。
  • 外部からは両者の保持するペアの共通数字が特定できないが、お互いには特定できているか。
  • お互い特定できないか。

解法

お互いに、自身の持つペアをNないしM通り全通り仮定した場合に、「自身がこのペアを持つ場合に、相手はこのペアなら1つ数字を共有している状態となる」となる相手のペアを列挙しよう。

自身の選択したペアに対し、あいてが共有した数字を持つペアが1つも無い場合、そもそも自身はそのペアを持ちえない。
…という処理を繰り返し、あり得ないペアを消していこう。

最後に互いが互いに共有数値を特定できるか判定していく。
互いの共有数値が1つに絞れるなら特定できるので1番目の形の解となる。
そうではないが、自身の各ペアに対し、相手の数字が特定できるなら2番目の形の解となる。

int N,M;
int A[12],B[12];
int MA[12];
int MB[12];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		A[i] = (1<<x) | (1<<y);
	}
	FOR(i,M) {
		cin>>x>>y;
		B[i] = (1<<x) | (1<<y);
	}
	
	vector<int> CA[12],CB[12];
	int a[2]={},b[2]={};
	FOR(i,N) FOR(j,M) if(__builtin_popcount(A[i]&B[j])==1) MA[i] |= 1<<j;
	FOR(i,M) FOR(j,N) if(__builtin_popcount(B[i]&A[j])==1) MB[i] |= 1<<j;
	
	FOR(i,1200) {
		FOR(x,N) if(MA[x]==0) FOR(y,M) MB[y] &= ~(1<<x);
		FOR(x,M) if(MB[x]==0) FOR(y,N) MA[y] &= ~(1<<x);
	}
	
	int cand=0;
	int cantsure=0;
	FOR(i,N) {
		int mc=0;
		FOR(j,M) if((MA[i]&(1<<j)) && (MB[j]&(1<<i))) {
			cand |= A[i]&B[j];
			mc |= A[i]&B[j];
		}
		if(__builtin_popcount(mc)>1) return _P("-1\n");
	}
	FOR(j,M) {
		int mc=0;
		FOR(i,N) if((MA[i]&(1<<j)) && (MB[j]&(1<<i))) {
			cand |= A[i]&B[j];
			mc |= A[i]&B[j];
		}
		if(__builtin_popcount(mc)>1) return _P("-1\n");
	}
	
	if(__builtin_popcount(cand)>1) {
		_P("0\n");
	}
	else if(__builtin_popcount(cand)==1) {
		FOR(x,10) if(cand & (1<<x)) cout<<x<<endl;
	}
	else {
		_P("-1\n");
	}
}

まとめ

問題文の理解に手間取った。