SRM 331 div1 level1 CarolsSinging

どんどん遡って練習してます。

スピード問題。Javaで最速の人を参考。

public int choose(String[] lyrics) {
       int res = 1000;
       int[] masks = new int[lyrics.length];
       int carols = lyrics[0].length();
       for (int i = 0; i < lyrics.length; i++)
           masks[i] = Integer.parseInt(
  lyrics[i].replace('Y', '1')
   .replace('N', '0'), 2);
       for (int m = 0; m < 1 << carols; m++) {
           boolean ok = true;
           for (int i = 0; i < masks.length; i++)
               if ((masks[i] & m) == 0) ok = false;
           if (ok && Integer.bitCount(m) < res)
  res = Integer.bitCount(m);
       }
       return res;
   }

• 文字列 "YYNNNY"をビット110001に変換
  

  Integer.parseInt(lyrics[i].replace('Y', '1')
   .replace('N','0'),2)

• 
  


• int の立っているビットを数える
  

  Integer.bitCount(m)



• ビットなんてものは後で何でもできるから、まずビット化し方法を採用してあとはループ。
  この場合、人毎にintを作って人ビットを作った方が早い。
  Carolsの組み合わせビットを使ってチェックするには
  一人一人 Carolsビット & 人ビットを取って、一人も０にならないCarolsビットを採用