kmjp's blog

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

TopCoder SRM 621 Div2 Hard MixingColors

これは割と簡単だと思う。
http://community.topcoder.com/stat?c=problem_statement&pm=10409

問題

絵を描くためにN色の絵の具が必要であり、それぞれの絵の具の色は整数値color[i]である。

2つの色の絵の具を混ぜることで、両者のxorの値を取る新しい色が生成できる。
各色の絵の具が無限にある店で絵の具を買う際、color[i]を全て生成するのに必要な最小の色の数Mを答えよ。

解法

各color[i]の2進数表現した各桁の値により、color[i]の値からGF(2)のベクトルに変換する。
例えば2進数で5桁までを考える場合、color[i]=5(101b)なら(0,0,1,0,1)、color[i]=30(1110b)なら(1,1,1,1,0)というベクトルであると考える。

あるM色から上記N個のベクトルが生成できるということは、上記ベクトルを並べた行列のrankがM以下であることを示す。
よって最小のMを求めるには行列のrankを求めればよい。

ついでなので、templateつけてライブラリ化しておいた。

template<class C> int gf2_rank(vector<C>& V) { 
	int i,j;
	int N=V.size();
	FOR(i,N) {
		sort(V.begin()+i,V.end(),greater<C>());
		if(V[i]==0) break;
		C msb=1;
		while(msb<<1 <= V[i]) msb<<=1;
		for(j=i+1;j<N;j++) if(V[j]&msb) V[j]^=V[i];
	}
	return N-count(V.begin(),V.end(),0);
}

class MixingColors {
	public:
	int minColors(vector <int> colors) {
		return gf2_rank<int>(colors);
	}
}

まとめ

color[i]が独立なM個のベクトルの合成で生成できる、と考えればあっさり。