SRM600div2 Med ORSolitaireDiv2

SRM 競技プログラミング

今日からSRMdiv2med埋め開始(atcoderレート1469)

TopCoder Statistics - Match Overview

例えばgoal = 00101110の時、goalのbitが0となっている桁が1になっている数字は取り除く必要はない。 10001111は取り除く必要なし。00101000は取り除く可能性がある。 取り除く可能性がある数字の集合からgoalを作れないようにするには最小で何個の数字を取り除けば良いかという問題。

集合の数字にについて、桁ごとに1が立っている数字が何個あるか調べて、その最小値を答えれば良い。

class ORSolitaireDiv2{
  public: int getMinimum(vector <int> numbers, int goal) {
    int n = numbers.size();
    int ret = 1e9;
    int bit[30]; CLR(bit);
    FOR(i,0,n) {
      bool ok = true;
      FOR(j,0,30) {
        if((numbers[i]>>j)&1 && !((goal>>j)&1)) ok = false;
      }
      if(!ok) continue;
      FOR(j,0,30) {
        if((numbers[i]>>j)&1) bit[j]++;
      }
    }
    FOR(j,0,30) if((goal>>j)&1) ret = min(ret, bit[j]);
    return ret;
  }