kmjp's blog

競技プログラミング参加記です

TopCoder SRM 600 Div1 Easy ORSolitaire

SRM600に参加。久々にEasy/Medium両方を本番に通せてよかった。
Mediumは計算量の見積もりが甘くて一度resubmitしたけど、それでも600pt初めて通せたので上出来。
Easyが簡単だったため、部屋で誰もfailedしてなかったので、Challengeもノーチャンスでした。
http://community.topcoder.com/stat?c=problem_statement&pm=12888

問題

初期値をX=0とする。配列numbersに含まれている任意の数値とXのorを取ってXを更新し、最終的にXをgoalにするゲームを考える。

ここで、上記ゲームを邪魔し、numbersのうち幾つかの数値を削除してgoalに到達できないようにしたい。
最小でいくつ取り除けばよいか。

解法

まず、numbers中orしてしまうとgoalに含まれないbitがsetされる数値は、どうせ利用できないので無視する。
次にgoalに含まれる各bitにおいて、利用可能なnumbers中の数値のうち、そのbitがあるものの数を数える。
これは、このbitを立てさせないようにするために削除しないといけない数値といえる。
各bitのうち、bitが立っているものの最小値が答え。

class ORSolitaire {
	public:
	int getMinimum(vector <int> numbers, int goal) {
		vector<int> aa;
		ll N,i,j,r=100,x=0;
		
		FOR(i,numbers.size()) if((numbers[i] & ~goal)==0) x|=numbers[i],aa.push_back(numbers[i]);
		if(x!=goal) return 0;
		
		FOR(i,31) {
			if((goal & (1LL<<i))==0) continue;
			x=0;
			FOR(j,aa.size()) if(aa[j] & (1LL<<i)) x++;
			r = min(r,x);
		}
		return r;
	}
};

まとめ

今回は参加者も多いため、submit前にいつもよりまじめにチェックした。
Mediumが通せないとEasyの速さ勝負になるのであまりやりたくないのだが…。
今回はMediumが通ったので結果的にあまり関係なかったけどね。