ハンコ [yukicoder 387] - はまやんはまやんはまやん

問題

Nマスのハンコがあり、i個目のマス目にはaiの色がついている。
2*N-1マスの紙があり、この紙にハンコで色をつけていく。
ハンコで色をつけた情報は数列 bi で与えられる。
bi==1であれば、左からi個目のマスにハンコの左端を合わせてハンコを押したことを意味する。
それぞれのマスについて混ざった色の数の偶奇を求めよ。

1 <= N <= 10^5
1 <= ai <= 10^5

帰納的考察(Editorial見た)

1. 本番はさっぱり分からなかった。O(NlogN)で解くんだろうなとか思っていた
2. 遇奇判定という所がヒントだと思って考えていたけど無理だった

―――― 壁 ――――

kmjpさんのソースコードを拝見するのが最も良いです(kmjpさん崇拝なだけですが)。

3. 例を出してみる

ハンコ ABBBC
塗る所 10100

4. 問題文通り塗ってみる

000000000
↓ b0 == 1なので
  000000000
+)ABBBC
-----------
  ABBBC0000
↓ b2 == 1 なので
  ABBBC0000
+)  ABBBC
-----------
  ABABBBC00
    B C
となり、「奇奇偶奇偶奇奇偶偶」が答えです。

この方法だと
各マスについて同じ色で塗ったかを確認する必要がある
のが嫌な所ですね（自分はこの辺が解決できなかった）

5. なので「色に注目して塗ってみる」ことにします

A 10000
B 01110
C 00001
Aがつく部分は 101000000
Bがつく部分は 011111000
Cがつく部分は 000010100

各ビットに対して、1である個数の偶奇を判定すれば答えが導けます。
ビット列に対して1の個数の偶奇を判定するときは排他的論理和（XOR,C++で言えば演算子^）が使えます。

排他的論理和
左右の項が同じなら0,異なるなら1を返す演算。
例) 0^1 = 1, 0^1^1 = 0, 1^0^1^1^1^0 = 0
1の数が偶数なら0,奇数なら1となります

6. 各色に対して紙に塗られる場所を示すビット列を作ることができれば、あとはそれを排他的論理和でまとめれば答えが導ける
7. 最後の問題は、どうやって各色に対して紙に塗られる場所を示すビット列を作るか(この辺が難しい)

例のBについて考えてみる
(1) ハンコの1番目にはBが無い -> 無視
(2) ハンコの2番目にBがついている -> ハンコを押す所の1つ右がBで塗られる
(3) ハンコの3番目にBがついている -> ハンコを押す所の2つ右がBで塗られる
(4) ハンコの4番目にBがついている -> ハンコを押す所の3つ右がBで塗られる
(5) ハンコの5番目にはBが無い -> 無視
つまり、ハンコで押す所をずらすことで、塗られる場所が表現できることになる

(1) 00000
(2)  10100
(3)   10100
(4)    10100
(5)     00000
--------------
    011111000

ハンコの何番目で押されていても最低1回押されていれば、紙のあるマスは押されていることになる
このような少なくとも一回1があれば、1としたい場合は、論理和(OR,C++で言えば演算子|)が使えます。

論理和
左右の項がどちらも0なら0,それ以外なら1

8. 計算量的に怪しいのですが、この解法で通ります。まとめると以下のようになります。

まず、ハンコの何番目にその色があるかを各色毎にまとめる
各色頃にまとめたものを使って、7.で各色毎にその色がついている紙を表すビット列を作る
その全てのビット列に対し排他的論理和をとり、0と1によって答えを出す

長いビット長のビット計算となるので、bitsetを使いましょう。

実装

http://yukicoder.me/submissions/101416

int N;
vector<int> a[201010];
bitset<201010> BB;
//-----------------------------------------------------------------
int main() {
    scanf("%d", &N);

    int x;
    rep(i, 0, N) scanf("%d", &x), a[x].push_back(i);
    rep(i, 0, N) scanf("%d", &x), BB[i] = x;
    
    bitset<201010> ans;
    rep(i, 0, 201010) if (a[i].size()) {
        bitset<201010> BA;
        for (int j : a[i]) BA |= BB << j;
        ans ^= BA;
    }

    rep(i, 0, 2 * N - 1) {
        if (ans[i])
            printf("ODD\n");
        else
            printf("EVEN\n");
    }
}