yukicoder : No.387 ハンコ

bitsetが想像以上に速かった。
http://yukicoder.me/problems/no/387

問題

幅がNマス分のハンコがある。
各マスにはA[i]の色を塗ることができる。

このハンコを使って、横幅(2N-1)マス分の紙に色を塗る。
N要素の配列B[i]が与えられる。
B[i]=1なら、このハンコの左端がiマス目となるようにハンコを押す。
１つのマス目には重ねて複数の色を塗ることができる。

紙の各マスに対し、塗られた色の数の偶奇を求めよ。

解法

最初FFTかと思ったけど、同じ色を複数回塗る処理がうまく捌けないので諦めた。
求めるのが色数の偶奇だったので、bitsetを使った。

紙の各マスの色数の偶奇を(2N-1)bitのbitsetで管理しよう。
Bをbitsetで表記したものをBSとする。

ハンコ上同じ色のマスが複数個ある場合、それらをまとめて処理しよう。
同じ色A[i]=cとなるiがいくつかあるとする。

そのようなiに対し、(BS＜＜i)のbitwise-orを取ろう。
これでcの色を塗るマスが列挙できる。
これを答えを管理する上記(2N-1)bitのbitsetとbitwise-xorを取れば、求める各マスの色数の偶奇を更新することができる。

int N;
vector<int> V[101010];
bitset<202020> BS;
bitset<202020> TS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, V[x].push_back(i);
	FOR(i,N) cin>>x, BS[i]=x;
	
	FOR(i,101000) if(V[i].size()) {
		bitset<202020> T;
		FORR(v,V[i]) T |= BS<<v;
		TS ^= T;
	}
	FOR(i,2*N-1) _P("%s\n",TS[i]?"ODD":"EVEN");
	
}

まとめ

O(N^2/w) (wはWordsize)なので実行時間が結構厳しいかと思ったけど、1s位で通ってびっくりした。