Google Code Jam 2019 Round 1B - Draupnir

問題

codingcompetitions.withgoogle.com

素数 6 の数列  a_i がある。クエリとして D を出力すると、  \sum 2^(D/i) * a_i (\mod 2^63) が与えられる。クエリを 2 回投げた後に  a_i を出力せよ。

解法

 \mod 2^63 は入力を 64bit 整数に収めるためのものではなく、解法の重要なポイントになる。D=200 で得られる入力は  2^200 a_1 + 2^100 a_2 + 2^66 a_3 + 2^50 a_4 + 2^40 a_5 + 2^33 a_6 \equiv 2^50 a_4 + 2^40 a_5 + 2^33 a_6 (\mod 2^63) である。  a_i \leq 100 < 2^7 であることから  a_4, a_5, a_6 を求めることができる。これらを利用して D=50 の入力から  a_1, a_2, a_3 を求めることができる。

コード

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let t: usize = sc.read();
    let _: usize = sc.read();
    for _ in 0..t {
        println!("200");
        let day200: u64 = sc.read();
        let ring4 = day200 / (1 << 50);
        let ring5 = (day200 - ring4 * (1 << 50)) / (1 << 40);
        let ring6 = (day200 - ring4 * (1 << 50) - ring5 * (1 << 40)) / (1 << 33);

        println!("50");
        let day50: u64 = sc.read();
        let day50 = day50 - ring4 * (1 << 12) - ring5 * (1 << 10) - ring6 * (1 << 8);
        let ring1 = day50 / (1 << 50);
        let ring2 = (day50 - ring1 * (1 << 50)) / (1 << 25);
        let ring3 = (day50 - ring1 * (1 << 50) - ring2 * (1 << 25)) / (1 << 16);

        println!(
            "{} {} {} {} {} {}",
            ring1, ring2, ring3, ring4, ring5, ring6
        );

        let response: i64 = sc.read();
        assert_eq!(response, 1);
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}