けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。

問題へのリンク

問題概要

 N 要素の非負整数列  a_{1}, \dots, a_{N} が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。

  • index  i (i = 2, \dots, N-1) を 1 つ選んで、 a_{i-1} a_{i-1} XOR  a_{i} に置き換えて、 a_{i+1} a_{i+1} XOR  a_{i} に置き換える

制約

  •  1 \le N \le10^{5}

考えたこと

色々手を動かしていると

  • 同じ操作を 2 回連続すると元に戻る
  • ごちゃごちゃ色々な順序で操作しているとたまに元に戻る

といったあたりから、どことなく隣接 swap 操作に近い香りを感じる。きっと適切な変数変換を施すと隣接 swap 操作に一致しているに違いない。そういう系の問題には解き覚えがある。以下の問題だ。

drken1215.hatenablog.com

このときは、数列に対して階差をとる (imos 法的変換) と、なんと操作は swap 操作とみなせることが判明したのだ。今回は imos 法変換しても何も起こらなかった。が、累積 XOR をとると...!!!

a, b, c, d, e
→ a, b ^ c, c, c ^ d, e

という変換は、

a, a ^ b, a ^ b ^ c, a ^ b ^ c ^ d, a ^ b ^ c ^ d ^ e
→ a, a ^ b ^ c, a ^ b, a ^ b ^ c ^ d, a ^ b ^ c ^ d ^ e

という風になる。よく見ると「index i に対する操作」は「swap(a[i-1], a[i])」に一致していることがわかる。よって問題は次のように言い換えられた。


  • 数列 a の累積 XOR をとって得られる数列を s とする (ただし s[ 0 ] = a [ 0 ] となるようにする)
  • s の最終要素は固定して、それ以外については任意の入れ替えができる
  • s の階差数列が辞書順最小となるようにせよ

Binary Trie へ

ここまでくればやりたいことはわかる

  • まず s (の最終要素以外) のうち最小値をとる (それを v とする)
  • s 全体に v を XOR 加算して、その中での最小値をとる (それを再び v とする)
  • 以後それを繰り返す

ということがやりたい。よって次のことができるデータ構造が欲しい

  1. 挿入された要素の最小値を取得
  2. 挿入された要素全体に値 v を XOR 加算する
  3. データ構造から値 v を削除する

これができるデータ構造として Binary Trie がある。

#include <iostream>
#include <vector>
using namespace std;


// Binary Trie
template<typename INT, size_t MAX_DIGIT> struct BinaryTrie {
    struct Node {
        size_t count;
        Node *prev, *left, *right;
        Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}
    };
    INT lazy;
    Node *root;

    // constructor
    BinaryTrie() : lazy(0), root(emplace(nullptr)) {}
    inline size_t get_count(Node *v) const { return v ? v->count : 0; }

    // add and get value of Node
    inline void add(INT val) {
        lazy ^= val;
    }
    inline INT get(Node *v) {
        if (!v) return -1;
        INT res = 0;
        for (int i = 0; i < MAX_DIGIT; ++i) {
            if (v == v->prev->right)
                res |= INT(1)<<i;
            v = v->prev;
        }
        return res ^ lazy;
    }

    // find Node* whose value is val
    Node* find(INT val) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag) v = v->right;
            else v = v->left;
            if (!v) return v;
        }
        return v;
    }

    // insert
    inline Node* emplace(Node *prev) {
        return new Node(prev);
    }
    void insert(INT val, size_t k = 1) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag && !v->right) v->right = emplace(v);
            if (!flag && !v->left) v->left = emplace(v);
            if (flag) v = v->right;
            else v = v->left;
        }
        v->count += k;
        while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right);
    }
    
    // erase
    Node* clear(Node *v) {
        if (!v || get_count(v)) return v;
        delete(v);
        return nullptr;
    }
    bool erase(Node *v, size_t k = 1) {
        if (!v) return false;
        v->count -= k;
        while ((v = v->prev)) {
            v->left = clear(v->left);
            v->right = clear(v->right);
            v->count = get_count(v->left) + get_count(v->right);
        }
        return true;
    }
    bool erase(INT val) {
        auto v = find(val);
        return erase(v);
    }

    // max (with xor-addition of val) and min (with xor-addition of val)
    Node* get_max(INT val = 0) {
        INT nval = val ^ lazy;
        Node* v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (!v->right) v = v->left;
            else if (!v->left) v = v->right;
            else if (flag) v = v->left;
            else v = v->right;
        }
        return v;
    }
    Node* get_min(INT val = 0) {
        return get_max(~val & ((INT(1)<<MAX_DIGIT)-1));
    }
   
    // lower_bound, upper_bound
    Node* get_cur_node(Node *v, int i) {
        if (!v) return v;
        Node *left = v->left, *right = v->right;
        if ((lazy >> i) & 1) swap(left, right);
        if (left) return get_cur_node(left, i+1);
        else if (right) return get_cur_node(right, i+1);
        return v;
    }
    Node* get_next_node(Node *v, int i) {
        if (!v->prev) return nullptr;
        Node *left = v->prev->left, *right = v->prev->right;
        if ((lazy >> (i+1)) & 1) swap(left, right);
        if (v == left && right) return get_cur_node(right, i);
        else return get_next_node(v->prev, i+1);
    }
    Node* lower_bound(INT val) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag && v->right) v = v->right;
            else if (!flag && v->left) v = v->left;
            else if ((val >> i) & 1) return get_next_node(v, i);
            else return get_cur_node(v, i);
        }
        return v;
    }
    Node* upper_bound(INT val) {
        return lower_bound(val + 1);
    }
    size_t order_of_val(INT val) {
        Node *v = root;
        size_t res = 0;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            Node *left = v->left, *right = v->right;
            if ((lazy >> i) & 1) swap(left, right);
            bool flag = (val >> i) & 1;
            if (flag) {
                res += get_count(left);
                v = right;
            }
            else v = left;
        }
        return res;
    }

    // k-th, k is 0-indexed
    Node* get_kth(size_t k, INT val = 0) {
        Node *v = root;
        if (get_count(v) <= k) return nullptr;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (lazy >> i) & 1;
            Node *left = (flag ? v->right : v->left);
            Node *right = (flag ? v->left : v->right);
            if (get_count(left) <= k) k -= get_count(left), v = right;
            else v = left;
        }
        return v;
    }

    // debug
    void print(Node *v, string prefix = "") {
        if (!v) return;
        cout << prefix << ": " << v->count << endl;
        print(v->left, prefix + "0");
        print(v->right, prefix + "1");
    }
    void print() {
        print(root);
    }
    vector<INT> eval(Node *v, int digit) const {
        vector<INT> res;
        if (!v) return res;
        if (!v->left && !v->right) {
            for (int i = 0; i < get_count(v); ++i) res.push_back(0);
            return res;
        }
        const auto& left = eval(v->left, digit-1);
        const auto& right = eval(v->right, digit-1);
        for (auto val : left) res.push_back(val);
        for (auto val : right) res.push_back(val + (INT(1)<<digit));
        return res;
    }
    vector<INT> eval() const {
        auto res = eval(root, MAX_DIGIT-1);
        for (auto &val : res) val ^= lazy;
        return res;
    }
    friend ostream& operator << (ostream &os,
                                 const BinaryTrie<INT, MAX_DIGIT> &bt) {
        auto res = bt.eval();
        for (auto val : res) os << val << " ";
        return os;
    }
};

void AtCoderDwango5Honsen_B() {
    int N;
    cin >> N;
    vector<int> a(N), s(N), res(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        if (i == 0) s[i] = a[0];
        else s[i] = s[i-1] ^ a[i];
    }
    BinaryTrie<int, 30> bt;
    for (int i = 0; i < N-1; ++i) bt.insert(s[i]);
    for (int i = 0; i < N-1; ++i) {
        res[i] = bt.get(bt.get_min());
        bt.erase(res[i]);
        bt.add(res[i]);
    }
    res.back() = s.back() ^ bt.lazy;
    for (int i = 0; i < N; ++i) cout << res[i] << " ";
    cout << endl;
}

int main() {
    AtCoderDwango5Honsen_B();
}