CODE FESTIVAL 2016 Grand Final C - Cheating Nim

問題

C - Cheating Nim

解法

Grundy 数の原理から、「各 もしくは の XOR の値を 0 にすることが出来るか？出来るなら を使った回数は何回か？」という問題に言い換えることができます。

ここで、ある i について を使うと XOR の値 x は になります。すなわち、現在の XOR の値と の XOR をとった値になります。ところで は必ず の形になります。証明もできますが、実験でもわかります。なので、貪欲に上のビットから潰していくことで解けます。

コード

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.read();
    let a: Vec<u32> = (0..n).map(|_| sc.read()).collect();


    let mut xor_sum = 0;
    for &a in &a {
        xor_sum ^= a;
    }

    let mut ans = 0;
    for bit in (0..30).rev() {
        if ((1 << bit) & xor_sum) == 0 { continue; }
        let x = (1 << (bit + 1)) - 1;
        for &a in &a {
            let y = a ^ (a - 1);
            if y == x {
                xor_sum ^= y;
                ans += 1;
                break;
            }
        }
    }

    if xor_sum != 0 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024] }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' }

    fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]).parse().unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}