第5回 ドワンゴからの挑戦状 本選 B - XOR Spread

これを解けそうな人がCやDに突っ込んだからか、あまり解かれなかった。
B - XOR Spread

問題

長さNの整数列aが与えられる。以下の操作を何回でも繰り返せる:

  • 1 < i < Nなるiを選び、a[i-1] ^= a[i]; a[i+1] ^= a[i];を実行する。 (^= はXORを行って更新する処理を表す)

このとき、最終的に得られるaとして辞書順最小のものを求めよ。

  • 1 <= N <= 10^5
  • 0 <= a_i <= 10^9

解法

おもむろにb[i] = xor_{j <= i} a[j]という長さN+1の配列{b[0], b[1], ..., b[N]}を考えると、実は問題の操作はswap(b[i], b[i-1])と等価であることがわかる。つまり、b[1], ... ,b[N - 1]は自由に並べ替えることができる。
今回欲しいのは、対応するaが辞書順で最小の配列になるようなbである。そのため、まずa[1] = b[1]を最小化して、次にa[2] = b[2] xor b[1]が最小になるように残りの中からb[2]を選び、次にa[3] = b[3] xor b[2]が最小になるように残りの中から…ということを繰り返せばよい。
数の多重集合の中から与えられた数とのxorが最小になるものを選ぶのは、愚直にやるとO(多重集合のサイズ)時間かかるが、binary trieというデータ構造を使うことで1個あたりO(ビット数)時間でできる。また多重集合から要素を削除する必要もあるが、binary trieを使えば同様にO(ビット数)時間である。

実装上の注意点

  • a <= 10^9だから、trieにはデータを(少なくとも)31bit分保持する必要がある。
  • (Rust限定) どのデータの所有権を誰が持つかを考えてデータ構造を設計する必要がある。今回の場合木構造なので、親が子孫全ての所有権を持つと思うと自然に実装できる。

提出: Submission #3883421 - 第5回 ドワンゴからの挑戦状 本選 (Rust)

#[derive(Clone)]
struct Trie {
    ch: Vec<Option<Box<Trie>>>,
    count: i32,
    level: usize,
}

impl Trie {
    fn new(level: usize) -> Trie {
        Trie {
            ch: vec![None; 2],
            count: 0,
            level: level,
        }
    }
    fn add(&mut self, a: i32) {
        self.count += 1;
        let level = self.level;
        if level == 0 {
            return;
        }
        let bit = (a >> (level - 1) & 1) as usize;
        if self.ch[bit].is_none() {
            self.ch[bit] = Some(Box::new(Trie::new(level - 1)));
        }
        self.ch[bit].as_mut().unwrap().add(a);
    }
    fn min(&self, a: i32, acc: i32) -> i32 {
        assert!(self.count > 0);
        let level = self.level;
        if level == 0 {
            return acc;
        }
        let mut bit = (a >> (level - 1) & 1) as usize;
        let first_count = match self.ch[bit] {
            None => 0,
            Some(ref ch) => ch.count,
        };
        if first_count == 0 {
            bit = 1 - bit;
        }
        self.ch[bit].as_ref().unwrap().min(a, acc ^ (bit as i32) << (level - 1))
    }
    fn remove(&mut self, a: i32) {
        self.count -= 1;
        let level = self.level;
        if level == 0 {
            return;
        }
        let bit = (a >> (level - 1) & 1) as usize;
        assert!(self.ch[bit].is_some());
        self.ch[bit].as_mut().unwrap().remove(a);
    }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        a: [i32; n],
    }
    let mut b = vec![0; n + 1];
    for i in 0 .. n {
        b[i + 1] = b[i] ^ a[i];
    }
    let mut trie = Trie::new(31);
    for i in 1 .. n {
        trie.add(b[i]);
    }
    let mut ans = vec![0; n + 1];
    for i in 1 .. n {
        let next = trie.min(ans[i - 1], 0);
        ans[i] = next;
        trie.remove(next);
    }
    ans[n] = b[n];
    for i in (0 .. n).rev() {
        ans[i + 1] ^= ans[i];
    }
    for i in 0 .. n {
        puts!("{}{}", ans[i + 1], if i == n - 1 { "\n" } else { " " });
    }
}

まとめ

テスターをやった時は解法を思いつくまでに45分かかりました。