問題概要

2つの正の整数 $ n (\le 18) $ と $ x (\lt 2^n) $ が与えられる．次の 3 つの条件を満たす数列 $ a $ を構成せよ．

$ a $ の要素 $ a_i $ について， $ 1 \leq a_i \lt 2^n $ が成り立つ．
$ a $ の空でない部分列について，その部分列に含まれる要素の xor を取ったものが 0 でない，かつ $ x $ でもない．
上 2 つの条件を満たす数列のうち最長のものである．

解法概要

$ a $ の累積 xor を考える．$ b_i = a_1 $ から$ a_i $ までの累積 xor となるような数列を $ b $ とする．

$ a $ の $ l $ 番目から$ r $ 番目までの要素を切り出した部分列についての xor を考えるとき，

$ b_{l-1} \oplus a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = b_{r} $

が成り立つ．つまり

$ a_{l} \oplus a_{l+1} \oplus \cdots \oplus a_{r} = b_{l-1} \oplus b_{r} $ ．

したがって，問題の2番目の条件はこのように言い換えられる．

「 $ b $ に2回以上同じ値が登場せず，かつ，2つの値の xor を取ると $ x $ になるような値の組も登場しない．」

あとはこの条件にしたがって， $ b $ にできるだけ多くの数を詰め込み， $ b $ にしたがって $ a $ を作るだけである．

$ a_1 = b_1 $ を除けば， $ a_i = b_{i-1} \oplus b_i $ で求めることができる．

長さ $ 2^{18} $ の vector を用意しようとしたら Runtime Error を食らったので， set にすでに使った値を入れておいて find メソッドで値 i を使って良いかどうか判定するようにした．

ソースコード

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n, x;
    cin >> n >> x;

    vector<int> b;
    set<int> st;
    st.insert(0);
    for(int i=1;i<(1<<n);++i) {
        if(st.find(i) != st.end() || st.find(i^x) != st.end()) continue;
        b.push_back(i);
        st.insert(i);
    }

    int m = b.size();
    cout << m << endl;
    if(m) {
        cout << b[0];
        for(int i=1;i<m;++i){
            cout << " " << (b[i-1]^b[i]);
        }
        cout << endl;
    }
}

所感

結構典型っぽいのに全然わからなかったので反省．

NoiminのNoise

Codeforces Round #563 (Div. 2) D. Ehab and the Expected XOR Problem

問題概要

解法概要

ソースコード

所感