SRM 331 Div2 Medium CarolsSinging

問題

クリスマスでみんなで曲を歌おうとしている.それぞれ歌える曲と歌えない曲がわかっている時,すべての人が少なくとも1回は歌うことが出来る曲集合の最小サイズを求めよ.

解答

歌うことが出来る曲を1,出来ない曲を0とし,つかう曲を0, 1で表現すると,それぞれをa, bとするとa&b!=0ならば少なくとも1曲を歌える.全ての曲集合に対して,全ての人が少なくとも1曲は歌えるかどうかを判定して,その中の最小値を返す.

class CarolsSinging
{
public:
  int choose(vector <string> lyrics)
    {
      int n = lyrics.size();
      int m = lyrics[0].size();
      vector<int> ly(n, 0);
      int i, j;
      for(i = 0; i < n; i++){
        int tmp=0;
        for(j = 0; j < m; j++){
          tmp <<= 1;
          if (lyrics[i][j] == 'Y')
            tmp += 1;
        }
        // cout << lyrics[i] << " " << tmp << endl;
        ly[i] = tmp;
      }
      int res = m;
      for(i = 1; i < 1<<m;i++){
        bool correct = true;
        for(j = 0; j < n; j++){
          if ((ly[j] & i) == 0) {
            correct = false;
            break;
          }
        }
        if (correct){
          int count = 0;
          for(j = i; j > 0;j/=2){
            if (j&1)count++;
          }
          // cout << "i=" << i << " count=" << count << endl;
          res = min(res, count);
        }
      }
      return res;
    }
};