TopCoder SRM 600 Div1 Easy ORSolitaire

問題

n個の数字が与えられる。
そこから数字をいくつか削除して、残った数字から
どのように数字を選んでそれら全てのbitwise orをとってもgoalの数字にできないようにしたい。

最小でいくつの数字を削除しなければならないか求めよ。

制約条件

数字≦10億
n≦50

方針

まずgoalで立ってないビットが立っている数字は無視してよい。
orを取ってもgoalが作れなくなるとき、どこか一つの桁の1は必ず立てられなくなる。


その桁を決め付ける。で、その桁のビットが立っている数字を全部消す。
これを全ての桁に関して見て、一番少なかった奴を答えにすればいい。

ソースコード

class ORSolitaire {
	public:
	int getMinimum(vector <int> numbers, int goal) {
		int n = numbers.size();
		int ans = inf;
		vi v;
		
		rep(i, n){
			if((~goal) & numbers[i]) continue;
			v.pb(numbers[i]);
		}
		rep(i, 31) if(goal >> i & 1){
			int cnt = 0;
			rep(j, v.size()) if(v[j] >> i & 1) cnt++;
			ans = min(ans, cnt);
		}
		return ans;
	}
};