Codeforces 442A : Borya and Hanabi

問題リンク : Problem - 442A - Codeforces

問題概要 :
Aliceはn枚のカードを持っている
カードは色と値を持っている
色は{'R','G','B','Y','W'} のいずれかで
値は{'1','2,'3','4','5'}　のいずれか
Aliceはn枚のカードをランダムにシャッフルした後、机の上に一直線上にならべた
Aliceはn枚のカード全てを知っているが、ランダムにシャッフルしたためその順番は分からない
貴方は一直線上にカードが並べられた後、それらのカードを確認したためどこにどのカードがあるか知っている
貴方はAliceに対して、
1. １つの色を指定し、その色をもつカードの場所を全て教える
2. １つの値を指定し、その値をもつカードの場所を全て教える
Aliceが全てのカードの位置を理解するために必要な教える回数の最小値を求めよ

解法 :
色と値は合わせて１０しかないので
どれを教えるのか全て2^10試す
どれを教えるか決めた後、
1. 色と値の両方を教えられたカードを全て除外する
2. 色を教えられたもののうち、値が1種類しかないなら除外する
3. 値を教えられたもののうち、色が1種類しかないなら除外する
これを更新ができなくなるまでループさせ、終わったときに全てのカードを知っているかどうかで判定する

コード :

#include<bits/stdc++.h>

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

using namespace std;

int n;
string cards[200];
char figure[] = {'R','G','B','Y','W','1','2','3','4','5'};

void compute(){
  int mini = INT_MAX;
  rep(bitmask,(1<<10)) if( __builtin_popcount(bitmask) < mini ){
    set<char> use;
    rep(i,10) if( (bitmask>>i) & 1 ) use.insert(figure[i]);

    vector<bool> knows(n,false);
    bool update = true;
    map<char,int> counter;
    rep(i,n) rep(j,2) ++counter[cards[i][j]];
    int remain = n;
    while( update ){
      update = false;

      set<string> S;
      rep(i,n) if( !knows[i] ) S.insert(cards[i]);
      if( S.size() <= 1 ) {
        rep(i,n) knows[i] = true;
        break;
      }

      rep(i,n) if( !knows[i] ) {
        if( use.count(cards[i][0]) && use.count(cards[i][1]) ) {
          --remain;
          update = true;
          --counter[cards[i][0]];
          --counter[cards[i][1]];
          knows[i] = true;
        }
      }
      
      rep(i,n) if( !knows[i] ) {
        if( use.count(cards[i][0]) ) {
          bool success = true;
          vector<int> pos;
          pos.push_back(i);
          rep(j,n) if( i != j && !knows[j] ) {
            if( cards[i][0] == cards[j][0] ) {
              if( cards[i][1] == cards[j][1] ) pos.push_back(j);
              else {
                success = false;
                break;
              }
            }
          }
          if( success ) {
            rep(j,pos.size()) knows[pos[j]] = true;
            update = true;
          }
        } else if( use.count(cards[i][1]) ) {
          bool success = true;
          vector<int> pos;
          pos.push_back(i);
          rep(j,n) if( i != j && !knows[j] ) {
            if( cards[i][1] == cards[j][1] ) {
              if( cards[i][0] == cards[j][0] ) pos.push_back(j);
              else {
                success = false;
                break;
              }
            }
          }
          if( success ) {
            rep(j,pos.size()) knows[pos[j]] = true;
            update = true;
          }
        } else {
          if( remain == 1 ) {
            knows[i] = true;
            update = false;
            break;
          }
        }
      }
      
    }
    bool success = true;
    rep(i,n) success &= knows[i];
    if( success ) mini = min(mini,__builtin_popcount(bitmask));
  }
  cout << mini << endl;
}

int main(){
  cin >> n;
  rep(i,n) cin >> cards[i];
  compute();
  return 0;
}