これは割と簡単だと思う。
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個のベクトルの合成で生成できる、と考えればあっさり。