bitsetが想像以上に速かった。
http://yukicoder.me/problems/no/387
問題
幅がNマス分のハンコがある。
各マスにはA[i]の色を塗ることができる。
このハンコを使って、横幅(2N-1)マス分の紙に色を塗る。
N要素の配列B[i]が与えられる。
B[i]=1なら、このハンコの左端がiマス目となるようにハンコを押す。
1つのマス目には重ねて複数の色を塗ることができる。
紙の各マスに対し、塗られた色の数の偶奇を求めよ。
解法
最初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位で通ってびっくりした。