Codeforces 488 Div2 D Open Communication - ちゃっくのメモ帳

Readforces
まず問題文が理解できなかった

問題概要

http://codeforces.com/contest/994/problem/D

A君とB君が数字のペアを持っている。A君とB君の数字のペアは共通する数字をちょうど1個含んでいる。
A君とB君はお互いの持っているペアを知らないので、互いに自分の持っているペアを含んだ数字のペアの集合を送信する。(つまりA君がペア(a,b)を持っていたら{(a,b),(c,d),(e,f)}のような集合を送信する)

A君とB君の送信したペアの集合から第三者C君が二人の保持しているペアに共通する数字を推測できるか?を答えよ。

推測できるならばその共通する数字を出力。
C君には推測できないが、A君とB君は共通する数字を推測できるならば0を出力。
それ以外の場合は-1を出力せよ。

多分こんな感じの問題(uwiさんに教えてもらった)

AさんとBさんがいくつかの数字のペアを見せ合います。各々の数字のペアはどれか1個だけが本物で、Aさんの本物とBさんの本物は1個だけ数が共通です。いま見せあった結果が与えられるので、
— 有為 (@uwitenpen) June 16, 2018

@chakku_000
本物がわかってない状態からでも共通の値がわかるか、
上記以外で、片方の本物がわかっている状態から共通の値が特定できるか
上記以外か
を判定してください的な
— 有為 (@uwitenpen) June 16, 2018

解法

まずA君の視点に立って「仮に自分がこのペアを持っている場合、相手とはどの数字を共有するか?」を考える。A君のペア(a,b)に対して共通する可能性のある数字が2つ(a,bの両方の場合)はA君がそのペア(a,b)の場合には共通数字がわからないので-1を出力して終了。もし共通数字の可能性がある数字が1つならば、その数字を"共通数字候補A"に入れる。
同様のことをB君に対しても行う。

"共通数字候補A"と"共通数字候補B"が共通する数字を1つしか持っていないならばC君はそれが共通数字であることがわかる。
もし"共通数字候補A,B"が共通する数字を2つ以上もっているならば、C君は推論ができないので0を出力すれば良い。

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n,0),b(m,0);
    for(int i=0;i<n;i++){
        int x,y; cin >> x >> y;
        a[i] |= (1<<x);
        a[i] |= (1<<y);
    }
    for(int i=0;i<m;i++){
        int x,y; cin >> x >> y;
        b[i] |= (1<<x);
        b[i] |= (1<<y);
    }

    int ac=0,bc=0;
    rep(i,n){
        int cand = 0;
        rep(j,m) if(__builtin_popcount(a[i]&b[j]) == 1){
            cand |= a[i] & b[j];
        }
        int cnt = __builtin_popcount(cand);
        if(cnt == 0) continue;
        else if(cnt == 1){
            ac |= cand;
        }
        else if(cnt > 1){
            cout << -1 << endl;
            return 0;
        }
    }
    rep(i,m){
        int cand = 0;
        rep(j,n) if(__builtin_popcount(b[i]&a[j]) == 1){
            cand |= b[i] & a[j];
        }
        int cnt = __builtin_popcount(cand);
        if(cnt == 0) continue;
        else if(cnt == 1){
            bc |= cand;
        }
        else if(cnt > 1){
            cout << -1 << endl;
            return 0;
        }
    }

    if(__builtin_popcount(ac & bc) == 1){
        for(int i=0;i<20;i++){
            if((1<<i) & (ac & bc)){
                cout << i << endl;
                return 0;
            }
        }
    }else{
        cout << 0 << endl;
    }
}

感想

なんか難しく感じるけど、直感の優れてる人なら自明で一瞬な気がする。
C君がA君の立場、B君の立場に立って考えたり、A,B君がお互い他方の立場にたって考えたりすればもう少し正確に推測されるような気がしたが、そういう推論で消されるのは「片方から見たら共通数字があるが、もう片方からしたら共通数字がない」パターンだが、2つのペアに対して共通数字がある場合はお互いどちらからしても共通数字があるのでこのタイプのパターンは存在しないってことになかなか気がつけなかった