第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分かかりました。