制限が小さいことでだいぶ戸惑った。
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"); } }
まとめ
問題文の理解に手間取った。