AtCoder Beginner Contest 126 XOR Matching 別解
問題: 非負整数 M (≤17) と非負整数 K (≤109) が与えられる。以下の条件を満たす0 ~ 2M の数列が存在するか判定し、存在するなら一例を示せ。
例えばM = 3、K=4について考えてみる。このとき、
0 1 2 3 4 5 6 7
を使用することになる。
ここで、xorによって4を作ることができるペアは４つあることに気づく。
0 4 1 5 2 6 3 7
それぞれのペアをA, B, C, Dと呼ぶことにする。
またそれぞれのペアを逆順にした
4 0 5 1 6 2 7 3
をA' B' C' D'と呼ぶことにする。
すると、
A B C D C' B' A' D'のように並べたものが答えとなる。
これは数列0 4 1 5 2 6 3 7 6 2 5 1 4 0 7 3
に相当する。
理由
例えばCとC'はDを挟んでおり、BとB'はC/D/Cを挟んでおり、AとA'はB/C/D/C/Bを挟んでおり、DとD'はC/B/Aを挟んでいる。 つまり、これらのアルファベットの組はいずれもxorによって4を作るペアを奇数個挟んでおり、それらの全てのxorはやはり4となる。
またA'-D'を使わないとすると、
A B C D C B A D
と並べてしまうが、
これは数列0 4 1 5 2 6 3 7 2 6 1 5 0 4 3 7
となり、例えば、6の間に3と7と2が入ってしまう。3 xor 7は4になるのに2が邪魔である。
したがって、二度目に同じペアが現れるときは順番を反対にする必要がある。
例えば2 6 3 7 6 2とすると、6の間には3と7しか存在せず、3 xor 7=4が残る。
7の間には6が二回表れてそれらは打ち消し合うので、やはり3 xor 7=4が残る。
4でない数字、たとえば4ではなくて7の場合も同様で、 xorによって7を作ることができるペアは以下の４つである。
0 7 1 6 2 5 3 4
となる。このように1-7の全ての数字に対し４つのペアが必ず定まる(M = 3の場合)。
ちなみにa xor b = kとなるaの相方bを見つけるためには a xor kを計算すれば良い。
M=4の場合
8個のペアを見つけ、
A B C D E F G H G' F' E' D' C' B' A' H'
とならべる、このような規則で任意のM(≧2)について構成できる。
コーナーケース
k=0については
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7
のように同じ数字を二個連続で並べればよい。
また、M=1の場合、k≧1を作ることが出来ない。
また、M≧2の場合、k≧2Mは作ることが出来ない。
実装(Rust)
use std::collections::*; fn print_array<T: std::string::ToString>(array: &Vec<T>) { println!( "{}", array .iter() .map(|ref x| x.to_string()) .collect::<Vec<_>>() .join(" ") ); } fn main() { let v = read_vec::<usize>(); let (m, k) = (v[0], v[1]); if k == 0 { let mut answers = vec![]; for i in 0..1 << m { for _ in 0..2 { answers.push(i); } } print_array(&answers); return; } if k >= 1 << m || (m == 1 && k != 0) { println!("-1"); return; } let nums = (0..1 << m).collect::<Vec<_>>(); let mut used = HashSet::new(); let mut pairs = Vec::new(); let mut reversed_pairs = Vec::new(); for &num in nums.iter() { if used.contains(&num) { continue; } let pair = (num, num ^ k); used.insert(num); used.insert(num ^ k); pairs.push(pair); let pair = (num ^ k, num); reversed_pairs.push(pair); } let mut answers = vec![]; for i in 0..pairs.len() { let pair = pairs[i]; answers.push(pair.0); answers.push(pair.1); } for i in (0..pairs.len() - 1).rev() { let pair = reversed_pairs[i]; answers.push(pair.0); answers.push(pair.1); } let final_reversed = reversed_pairs[reversed_pairs.len() - 1]; answers.push(final_reversed.0); answers.push(final_reversed.1); print_array(&answers); } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() }
感想
想定解法の方はもっとエレガントで楽そうでした。はい。
