ORSolitaire - TopCoder SRM Div1 #600 Easy

これは解ける．223.84pt(Practice)

解法

まず，各整数がgoalをつくるのに使えるかを調べる．
整数nがn | ~goal = 0を満たすならば，nはgoalをつくるのに使える．
(等式を満たさないならば，goalにない1の立つビットができてしまう．)
満たす整数のORをとり，goalにならなければ，そもそもできないので，0を出力する．
そうでなければ，goalの1であるビットに着目する．そのビットが1である整数をすべて削除すれば，goalをつくることはできない．よって，各ビットに対し，そこが1である整数を数えて，その最小の個数を求めればいい．

コード

class ORSolitaire {
public:
    int getMinimum(vector<int> numbers, int goal) {
        int x = 0;
        std::vector<int> v;
        for(int n : numbers){
            if(n & ~goal){continue;}
            x |= n;
            v.push_back(n);
        }

        if(x != goal){return 0;}
        
        int res = 252521;
        for(int i=0;i<=30;i++){
            if(!(goal >> i & 1)){continue;}
            int c = 0;
            for(int j : v){
                if(j >> i & 1){++c;}
            }
            res = std::min(res, c);
        }

        return res;
    }
};