yukicoder No.387 ハンコ

https://yukicoder.me/problems/no/387

問題概要

Nマスが横に連なったハンコがあり、マスiには色Aiのインクがついている。(2N-1)マスの紙に対し、はじめこのハンコを左端が合うように置き、「ハンコを押すor押さない」→「ハンコを右に1マスずらす」という操作をN回繰り返す。各操作においてハンコを押すか押さないかは0/1の数列Bとして与えられる。紙の(2N-1)の各マスにおいて、最終的に押される色数の偶奇を答えよ。

N, A <= 105

解法

  • 同じ色は何回押しても1色とカウントされる → orっぽい
  • 押される色数の偶奇を知りたい → xorっぽい

ということからビット操作に落とせないか考える。

まずハンコ側の視点で考えると、ハンコ側のマスiが紙側のどのマスに押されることになるかは、単純にビット列Bをiだけシフトさせればわかる(B=101のとき、ハンコの0マス目は紙の0マス目、2マス目に押される。ハンコの1マス目は2マス目、4マス目に押される。…)。よって、同じ色のマスについてこのビット列のbitwise orをとれば、最終的にその色が押されるマスを出すことができる。あとはすべての色についてそのビット列を計算し、bitwise xorをとっていけばあるマスに押される色数の偶奇を出すことができる。

ビット列の長さが 2N-1 なので各操作にO(N)かかりO(N2)となるが、ビット操作にC++のbitsetみたいなのを使うとワード長分(?)定数倍高速化がかかって 1010 / 64 ≒ 108 くらいになって間に合うようになる。

感想

AtCoderでは絶対出ないタイプの問題だけど、前にhackerrankか何かでもN=105でO(N2)をbitsetドーンが想定解なのを見たことあるなあ

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

int N;
int A[101010];
int B[101010];
bitset<202020> bs;
bitset<202020> ans;
bitset<202020> tmp;
vector<int> rev[101010];

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];

    REP(i, N) rev[A[i]].push_back(i);
    REP(i, N) bs[i] = B[i] == 1;

    REP(c, 101010) {
        tmp = 0;
        for (auto i: rev[c]) 
            tmp |= (bs << i);
        ans ^= tmp;
    }

    REP(i, 2*N-1) cout << (ans[i] ? "ODD" : "EVEN") << "\n";
}