Hatena::Grouptopcoder

kuuso1の日記

2014-05-28

SRM621 Div2 Hard

| 02:20 | SRM621 Div2 Hard - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM621 Div2 Hard - kuuso1の日記

  • intの配列colorsが与えられる。数値は絵具の色を表す。
  • 店があり、そこではあらゆる色を買うことができる。
  • また、2つの色x,yから新しい色x^y(排他的論理和XOR)を作ることができる。
  • colorsのすべての色を得るために必要な色数の最小値を求める。

(制約)1≦colorsのサイズ≦50, 1≦色の範囲≦1e9

本番中解けなかったが漠然と「32色あれば絶対足りるやん」と思っていた。

Editorialを読む。「If xor was modulo 2 vector addition」目からウロコである。

もうちょっと数学の言葉に書き直したのが↓

f:id:kuuso1:20140529021545p:image

なので掃き出し法で計算すればよい。ここで、通常の掃き出し方なら

・最上行の最左項の係数が1になるように最上行全体を割る

・それより下の行に、最左項と同じ列に非零数がある場合は最上行に係数を掛けたものを引いて零にする

を繰り返すが、 Z/2Zなので掛け算はなく、ただXORで最上行を足してやれば

他の行の最上位ビットを零化することができる。

public class MixingColors {
	public int minColors(int[] colors) {

		int N=colors.Length;
		Array.Sort(colors,(x,y)=>x>y?-1:(x<y?1:0));
		
		for(int i=0;i<N;i++){
			int cnt=0;
			if(colors[i]==0)continue;
			
			for(int j=0;j<32;j++){
				if((colors[i]&(0x1<<j))!=0)cnt=j;
			}
			for(int j=i+1;j<N;j++){
				if((colors[j]&(0x1<<cnt))!=0){
					colors[j]=colors[j]^colors[i];
				}
			}
			//掃き出しで消えてしまった行をswapする手間を
			//Nが小さいので sortで片づけている(下行へ追いやる)
			Array.Sort(colors,(x,y)=>x>y?-1:(x<y?1:0));
		}
		
		int ans=0;
		for(int i=0;i<N;i++)if(colors[i]!=0)ans++;
		
		return ans;
	}
}

掃き出し法初めて書いたが、掃き出し法デビューとしてはいささかマニアック。

あと最近XORにまつわる問題がたまたま重なっていたので、これはかなり自分の中で一つ光明がさした気がします。