2020-02-29

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

AtCoder AtCoder800点 unrated公式コン操作数列操作:swap 操作:隣接swap 変数変換して扱いやすい同型な問題を見出す条件の言い換え辞書順 trie木 BinaryTrie XOR いもす法的変換データ構造順列を題材とした問題操作後の結果の最適化問題操作を好きな回数だけ行える操作:上書き順列テク:順列は互換(swap操作)の積として表せる階差数列

操作を言い換えるところは楽しいけど、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 とする)
以後それを繰り返す

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

挿入された要素の最小値を取得
挿入された要素全体に値 v を XOR 加算する
データ構造から値 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();
}