SRM 600 Div2 Medium ORSolitaire

問題

SRM 600 - TopCoder Wiki

数字が書かれたカードが与えられて,そのカードを幾つか選択してORを取って,与えられた数字goalを作るゲームを考える. どうやってもそのようなgoalを作れないようにするためには最低何枚のカードを抜き取る必用があるかを答える問題

解答

  • goalで1が立っていないビットに1がたっているカードを使うとgoalは必ず作れないので,これらのカードは抜き取る候補から除外する.
  • 全てのカードを見ても,goalで1が立っている何れかのビットが1にならないようにカードを抜き取ればgoalは作れなくなる.
  • 今求めたいのは最小の抜き取るカード数なので,全てのカードでgoalで1が立っているビットの分布を調べ,最小の値がカードの抜き取る最小回数となる.
class ORSolitaireDiv2
{
public:
  int getMinimum(vector <int> numbers, int goal)
    {
      vector<int> candidates;
      for(int i = 0; i < numbers.size(); i++) {
        if (((~goal) & numbers[i]) == 0) {
          candidates.push_back(numbers[i]);
          // std::cout << numbers[i] << std::endl;
        }
      }
      int min_num_bit = 64;
      for (int i = 0; i < 32; i++) {
        if (!((goal >> i) & 1)) continue;
        int num_bit = 0;
        for (int j = 0; j < candidates.size(); j++) {
          if ((candidates[j] >> i) & 1) {
            num_bit++;
          }
        }
        // std::cout << "i=" << i << " num_bit=" << num_bit << std::endl;
        min_num_bit = min(min_num_bit, num_bit);
      }
      return min_num_bit;
    }
};