VSCode で Rust で競技プログラミングをするときの設定

拡張機能と RLS を入れる

task の登録

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558 
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "label": "cargo run",
            "type": "shell",
            "command": "RUST_BACKTRACE=1",
            "args": [
                "cargo",
                "run",
                "--bin",
                "${fileBasenameNoExtension}"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

スニペットの登録

{
	// Place your snippets for rust here. Each snippet is defined under a snippet name and has a prefix, body and 
	// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
	// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
	// same ids are connected.
	// Example:
	// "Print to console": {
	// 	"prefix": "log",
	// 	"body": [
	// 		"console.log('$1');",
	// 		"$2"
	// 	],
	// 	"description": "Log output to console"
	// }
	"Scanner and main": {
		"prefix": "scanner",
		"body": [
			"fn main() {",
			"    let s = std::io::stdin();",
			"    let mut sc = Scanner { stdin: s.lock() };",
			"}",
			"",
			"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()",
			"    }",
			"}"
		]
	}
}

今日解いた問題

問題

atcoder.jp

T経過後の蟻の位置は分かるので、蟻0がどの位置に対応するかを考える。これは座標0を通過した蟻の数で分かる。

コード

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let l: usize = sc.read();
    let t: usize = sc.read();
    let xw: Vec<(usize, usize)> = (0..n).map(|_| (sc.read(), sc.read())).collect();

    let mut clockwise = 0;
    let mut counter_clock_wise = 0;
    for (x, w) in xw.iter().cloned() {
        if w == 1 {
            clockwise += (x + t) / l;
        } else if t > x {
            counter_clock_wise += ((l - x) + t - 1) / l;
        }
    }

    let mut next = xw
        .into_iter()
        .map(|(x, w)| {
            if w == 1 {
                (x + t) % l
            } else {
                (l - ((l - x) + t) % l) % l
            }
        })
        .collect::<Vec<_>>();
    next.sort();
    let over = clockwise % n + n - counter_clock_wise % n;
    for i in 0..n {
        println!("{}", next[(i + over) % n]);
    }
}

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()
    }
}

問題

atcoder.jp

1マス進むと時間が1経過し、時間Kごとに扉を開けてもいいパワーがK部屋分だけ補充されると考える。

コード

use std::cmp;
use std::collections::VecDeque;

const INF: i32 = 1e9 as i32;
const DIR: [(i32, i32); 4] = [(0, -1), (0, 1), (-1, 0), (1, 0)];

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let k: i32 = sc.read();
    let board: Vec<_> = (0..h).map(|_| sc.chars()).collect();
    let mut dist = vec![vec![INF; w]; h];

    let mut si = 0;
    let mut sj = 0;
    for i in 0..h {
        for j in 0..w {
            if board[i][j] == 'S' {
                dist[i][j] = 0;
                si = i;
                sj = j;
            }
        }
    }

    let mut q = VecDeque::new();
    q.push_back((0, 0, si, sj));
    for _ in 0.. {
        let mut next_q = VecDeque::new();
        while let Some((time, open, i, j)) = q.pop_front() {
            if i == h - 1 || j == w - 1 || i == 0 || j == 0 {
                let turn = (time + k - 1) / k;
                println!("{}", turn);
                return;
            }
            for (di, dj) in DIR.iter().cloned() {
                let ni = (i as i32) + di;
                let nj = (j as i32) + dj;
                if ni < 0 || nj < 0 {
                    continue;
                }
                let ni = ni as usize;
                let nj = nj as usize;
                if ni >= h || nj >= w {
                    continue;
                }

                if board[ni][nj] == '#' && open > 0 && dist[ni][nj] > time + 1 {
                    dist[ni][nj] = time + 1;
                    if (time + 1) % k == 0 {
                        next_q.push_back((time + 1, k, ni, nj));
                    } else {
                        q.push_back((time + 1, open - 1, ni, nj));
                    }
                } else if board[ni][nj] == '.' && dist[ni][nj] > time + 1 {
                    dist[ni][nj] = time + 1;
                    if (time + 1) % k == 0 {
                        next_q.push_back((time + 1, k, ni, nj));
                    } else {
                        q.push_back((time + 1, open, ni, nj));
                    }
                }
            }

            let next_time = (time + k) / k * k;
            next_q.push_front((next_time, k, i, j));
        }
        q = next_q;
    }
}

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()
    }
}

問題

atcoder.jp

解説動画のとおりにやった。

1 ... a-1, a+1, ... , x
1 ... b-1, b+1, ... , x

という2つのほぼ等差数列から作れる積の最大値が ab を超えないような x を二分探索する。

コード

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let q: usize = sc.read();
    for _ in 0..q {
        let a: usize = sc.read();
        let b: usize = sc.read();
        let (a, b) = if a > b { (b, a) } else { (a, b) };

        let mut ok = a - 1;
        let mut ng = 1e10 as usize;
        while ng - ok > 1 {
            let x = (ok + ng) / 2;
            let mut max = 0;
            if x >= b - 1 {
                // 1 ... a-1    a+1   ... x-b+1 x-b+2 ... x
                // x ... x-a+2  x-a+1 ... b+1   b-1   ... 1
                max = get_max(1, a - 1, x, x + 2 - a);
                max = cmp::max(max, get_max(a + 1, x - (b - 1), x - (a - 1), b + 1));
                max = cmp::max(max, get_max(x + 2 - b, x, b - 1, 1));
            } else {
                // 1 ... a-1      a+1 ... x
                // x-1 ... x-a+1  x-a ... 1
                max = get_max(1, a - 1, x - 1, x - (a - 1));
                max = cmp::max(max, get_max(a + 1, x, x - a, 1));
            }

            if max < a * b {
                ok = x;
            } else {
                ng = x;
            }
        }
        println!("{}", if a <= ok { ok - 1 } else { ok });
    }
}

fn get_max(from_a: usize, to_a: usize, from_b: usize, to_b: usize) -> usize {
    if from_a > to_a {
        return 0;
    }
    assert_eq!(to_a + 1 - from_a, from_b + 1 - to_b);
    let mut m = (from_a + from_b) / 2;
    let mut max = cmp::max(from_a * from_b, to_a * to_b);
    if from_a <= m && m <= to_a {
        let da = m - from_a;
        let b = from_b - da;
        max = cmp::max(max, m * b);
    }
    m += 1;
    if from_a <= m && m <= to_a {
        let da = m - from_a;
        let b = from_b - da;
        max = cmp::max(max, m * b);
    }
    max
}

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()
    }
}

問題

atcoder.jp

すごく有名なパズル。

コード

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();

    let board: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut blue = vec![vec!['.'; w]; h];
    let mut red = vec![vec!['.'; w]; h];
    for i in 0..h {
        for j in 0..w {
            if j == 0 {
                red[i][j] = '#';
            } else if j == w - 1 {
                blue[i][j] = '#';
            } else if i % 2 == 0 {
                red[i][j] = '#';
            } else {
                blue[i][j] = '#';
            }

            if board[i][j] == '#' {
                red[i][j] = '#';
                blue[i][j] = '#';
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            print!("{}", red[i][j]);
        }
        println!();
    }
    println!();
    for i in 0..h {
        for j in 0..w {
            print!("{}", blue[i][j]);
        }
        println!();
    }
}

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()
    }
}

問題

atcoder.jp

上に重ねて色が塗られるので、クエリを逆から見ていく。

コード

use std::collections::VecDeque;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let m: usize = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }
    let q: usize = sc.read();
    let mut potential = vec![-1; n];
    let mut color = vec![0; n];
    let vdc: Vec<_> = (0..q)
        .map(|_| (sc.read::<usize>() - 1, sc.read::<i64>(), sc.read::<usize>()))
        .collect();

    for (root, distance, c) in vdc.into_iter().rev() {
        if potential[root] >= distance {
            continue;
        }
        let mut q = VecDeque::new();
        q.push_back(root);
        if color[root] == 0 {
            color[root] = c;
        }
        potential[root] = distance;
        while let Some(v) = q.pop_front() {
            if potential[v] == 0 {
                continue;
            }
            for &next in graph[v].iter() {
                if color[next] == 0 {
                    color[next] = c;
                }
                if potential[next] < potential[v] - 1 {
                    potential[next] = potential[v] - 1;
                    q.push_back(next);
                }
            }
        }
    }

    for c in color.into_iter() {
        println!("{}", c);
    }
}

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()
    }
}

Google Code Jam 2019 Round 1B - Fair Fight

問題

codingcompetitions.withgoogle.com

数列 \{c_i\} \{d_i\} が与えられる。 | max(c_l, c_{l+1}, ... , c_r) - max(d_l, d_{l+1} , ... , d_r)| \leq k  となるような (l, r) の組の数を求めよ。

解法

 | max(c_l, c_{l+1}, ... , c_r) - max(d_l, d_{l+1} , ... , d_r)| \gt k  となるような (l, r) の組の数を求めて全体から引くことにする。
 max(c_l, c_{l+1}, ... , c_r) - max(d_l, d_{l+1} , ... , d_r) \gt k    max(c_l, c_{l+1}, ... , c_r) - max(d_l, d_{l+1} , ... , d_r) \gt k  は c と d を入れ替えることで独立に同じように求めることができる。

各 i について c_i が最大となるような c の区間を求める。これは Sparse Table で二分探索を二回やると求まる。次に、この区間内で  max(d_l, d_{l+1}, ... , d_i) < c_i -k となるような l と  max(d_i, d_{i+1}, ... , d_r) < c_i -k となるような r を求める。

コード

use self::sparse_table::SparseTable;
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let t: usize = sc.read();
    for t in 0..t {
        let n: usize = sc.read();
        let k: i64 = sc.read();
        let c: Vec<i64> = sc.vec(n);
        let d: Vec<i64> = sc.vec(n);
        let ans = n * (n + 1) / 2 - solve(&c, &d, k) - solve(&d, &c, k);
        println!("Case #{}: {}", t + 1, ans);
    }
}

fn solve(c: &[i64], d: &[i64], k: i64) -> usize {
    let n = c.len();
    let c_st = SparseTable::from(c, 0, cmp::max);
    let d_st = SparseTable::from(d, 0, cmp::max);
    (0..n)
        .filter(|&i| d[i] < c[i] - k)
        .map(|i| {
            let mut ng = n + 1;
            let mut ok = i + 1;
            while ng - ok > 1 {
                let m = (ok + ng) >> 1;
                if c_st.get(i, m) <= c[i] {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            let right = ok;

            let mut ok = i as i64;
            let mut ng = -1;
            while ok - ng > 1 {
                let m = (ok + ng) >> 1;
                if c_st.get(m as usize, i) < c[i] {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            let left = ok;

            let mut ok = i + 1;
            let mut ng = right + 1;
            while ng - ok > 1 {
                let m = (ok + ng) >> 1;
                if d_st.get(i, m) < c[i] - k {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            let right = ok;

            let mut ok = i as i64;
            let mut ng = left - 1;
            while ok - ng > 1 {
                let m = (ok + ng) >> 1;
                if d_st.get(m as usize, i + 1) < c[i] - k {
                    ok = m;
                } else {
                    ng = m;
                }
            }
            let left = ok as usize;
            (i - left + 1) * (right - i)
        })
        .sum()
}

pub mod sparse_table {
    use std::cmp;

    pub struct SparseTable<T, F> {
        data: Vec<Vec<T>>,
        op: F,
    }

    impl<T, F> SparseTable<T, F>
    where
        T: Copy,
        F: Fn(T, T) -> T,
    {
        pub fn from(v: &[T], init: T, op: F) -> Self {
            let size = v.len().next_power_of_two();
            let count = size.trailing_zeros() as usize + 1;
            let mut data = vec![vec![init; size]; count];
            for (i, v) in v.iter().cloned().enumerate() {
                data[0][i] = v;
            }
            for c in 1..count {
                for i in 0..size {
                    let next = cmp::min(size - 1, i + (1 << (c - 1)));
                    data[c][i] = op(data[c - 1][i], data[c - 1][next]);
                }
            }

            Self { data: data, op: op }
        }

        /// get the result for [l, r)
        pub fn get(&self, l: usize, r: usize) -> T {
            assert!(l < r, "l={} r={}", l, r);
            let length = r - l;
            if length == 1 {
                return self.data[0][l];
            }
            let block_size = length.next_power_of_two() >> 1;
            let c = block_size.trailing_zeros() as usize;
            let left = self.data[c][l];
            let right = self.data[c][r - block_size];
            (self.op)(left, right)
        }
    }
}

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()
    }
}

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()
    }
}

Rust LT #4 で LT をした

rust.connpass.com

これに参加して5分枠で発表した。

テーマ決め

AtCoder Problems というサービスのバックエンドを Rust で書いていたので、それについて発表しようと思った。

github.com

技術的にはそこまで難しくなく、やっていることはドキュメントを読めば誰でもできるレベルなので話をするかは迷ったが、 Rust コミュニティの性質上、低レイヤーや言語仕様に関する発表が多いことが予想され、ライトな発表があってもよいだろうと考えた。サービス上にはクローラー、サーバーレス REST API、 DB 更新バッチの大きく分けて 3 つのアプリケーションが存在したが、サーバーレス API が身近で面白いだろうと考え、これについて話すことにした。

準備

いざスライドを作り始めてみると、想像以上に書くことがなく、AWS 公式ブログの内容を日本語訳しただけのスライドになってしまった。

aws.amazon.com

このブログにあるとおりに Lambda を組み、API Gateway でつなぎこんでやれば、本当に 5 分程度で Rust 製のサーバーレス API ができてしまう。つまりスライドを使って説明している間にデプロイで来てしまうのだ。というわけで、スライドを使った発表はやめ、実際に Rust + Lambda + API Gateway で作ってその場でデプロイすることにした。

実際に練習としてやってみると、crate のダウンロードやコンパイルに時間がかかって 5 分をオーバーしてしまったり、simple_logger や serde などを使っているおかげで見た目の複雑さが増していたりなど、発表する上での問題点を見つけた。これらについて、必要な crate はあらかじめコンパイルしておいたり、不要なコードは削除したりして対処した。

発表

実際に発表で書いた(コピペして削った)コードがこちら。

#[macro_use]
extern crate lambda_runtime as lambda;
use lambda::error::HandlerError;

use serde_json::{json, Value};

use std::error::Error;

fn main() -> Result<(), Box<dyn Error>> {
    lambda!(my_handler);

    Ok(())
}

fn my_handler(e: Value, c: lambda::Context) -> Result<Value, HandlerError> {
    let name = e
        .get("pathParameters")
        .unwrap()
        .get("name")
        .unwrap()
        .as_str()
        .unwrap();

    Ok(json!({
        "isBase64Encoded": false,
        "statusCode": 200,
        "body": format!("Hello {}!\n",name)
    }))
}

isBase64EncodedisBase64と書いてしまったおかげで Internal Server Error が発生してしまったときはもうダメかと思ったが、すぐに発見できたおかげで何とか完成にたどり着けた。ただ、入力部を実装する前に、バグからのデバッグ成功で会場が盛り上がってしまったので、入力部も含めて真に REST API にしていく部分が若干おまけっぽくなってしまった。次に発表するときは最初にゴールを明確にしておきたい。

AtCoder Jobs で転職した

prd-xxx.hateblo.jp

この記事を読んで思い出しましたが、僕も2ヶ月ほど前に AtCoder Jobs を利用して転職したので、その時のことを書きます。この転職に満足しているので、他の人が AtCoder Jobs を使う際の参考になれば幸いです。

AtCoder Jobs を使う前

前に働いていた会社 SoundHound Inc. は AI スピーカーを作っている会社で、G●●gle や Amaz●n と正面から競合していたので、「俺はレッドオーシャンで血で血を洗うような戦いがしてぇ!」と思って入社しました。しかし、意外にも事業は順調(これとかこれとかこれ)で、血で血を洗う感じではありませんでした。当初の予定通り戦いを求めて転職を考えましたが、周りに僕よりはるかに優秀な競技プログラマが何人もいて刺激がありましたし、給料が1300万円(ベース1100+ボーナス200)だったり、ストックオプションが束でついていたり、自分にとっては二度と出会えないのではないかと思えるほど待遇も良かったので、かなり迷いました。最終的には、20代で守りに入るようではニートだった頃の自分に顔向けできないと考えて、転職することにしました。

転職活動を始めたばかりの頃は AtCoder Jobs を使うことは考えておらず、知り合い経由で気になる会社をいくつか受けて祈られるなどして過ごしました。

AtCoder Jobs で転職活動

AtCoder Jobs では 2 社受けました。

A 社

ウェブサービスの会社の研究開発の部門に応募しました。

事前課題として問題が1問出題されました。提出期限は1週間後だったので、落ち着いて解けば良かったのですが、たまたまその問題を過去にコンテストで解いたことがあったので、勢いに任せて書き上げて提出しました。嘘解法でした。後で見てみたら、そのコンテストでも同じ嘘解法で通してました。全く成長していない…… その後の面接では、提出したコードについて全く触れられなかったのですが、どういう気持ちで見ていたのか未だに気になっています。

面接では、ネットワークのことからコンパイラのことまで幅広く質問されました。今までの仕事の中で身につけた知識や、競プロや趣味を通して得た知識で答えられる質問もありましたが、全く何を聞かれてるのか分からない質問もいくつかあり、全体的に厳しい印象でした。また、面接官が英語話者のこともあり、答えがわかっても英語で何と言えば良いか分からず、独自の言い回しを発明するシーンが多々ありました。外資で1年働くくらいで英語がどうにかなったりはしないですね…… その他、事前に提出していた経歴書に沿って質問されることもありましたが、経歴書に書いていた内容があまりに少なかったため、話す際に毎回基本的な前提から話すことになり、具体的に達成したことや技術的な工夫などまで面接時間内に話しきれないことが多かったです。

最終面接まで行きましたが、研究開発の部門では不採用ということになり、追加でバックエンド開発の部署の面接を受けました。こちらの面接は普通のウェブ系の面接という感じで、ホワイトボードコーディングなどをして、無難に終えることができ、オファーをもらうことができました。オファー内容は900万円+ボーナスで、「他の部署の面接であんなにボロボロだったのにこんなに良いオファー出していいの……?」と思わず言ってしまいました。

indeed

indeed の Search Quality という部署に応募しました。

面接前に AtCoder で問題を解く課題がありましたが、いつも通りのコンテスト形式だったので、A社の反省を踏まえて、とにかく落ち着いて取り組むことに集中しました。indeedJava を使う会社だということは事前の調べで分かっていたので、Rust で全完した後に Java で書き直して媚びておきました。

面接はオンライン1回とオンサイト3回があり、うち3回はコーディングインタビューでした。どの問題も、実際の業務でありそうな問題設定でありながら、面接官とディスカッションしながら解いていくうちに気づけば競プロ的な計算量改善ができている、という感じで面白かったです。残りの1回の面接では経歴書に沿って話したり、入社してからやりたい仕事などについて話したりしました。ここでもA社の反省を活かして、経歴書にはA4に収まる限りの情報を盛り込んでおいたので、面接時間を効率良く使うことができました(就活初心者か…?)。今回も英語話者の面接官がいましたが、A社の反省を踏まえて瞬間英作文をやり込んでおいたので、何とかなりました。最終的に1050万円+ボーナスでオファーが出ました。

A社もindeedも大規模なウェブサービスを実運用している会社でしたし、A社の方はボーナスが多いのと家賃補助があるのでindeedと待遇面での違いもあまりなく、どちらに行くかかなり迷いました。indeedで働いている知り合いに話を聞きに行ったときに強く勧められたことや、自分がJavaが好きなこと、G●●gle J●bs との新たな戦いを予感させることから、indeedに行くことにしました。

入社して

最初に感じたこととしては、開発サイクルがとても速いです。入社して最初の週で、実装とコードレビューを経て本番環境デプロイまでできたのには感動しました。開発サイクルを遅くしない工夫や、各人の仕事を可視化する工夫が随所にあり、日々学びがあります。

まとめ

AtCoder Jobs は平気で1000万円くらいの案件が流れてくる激ヤバ転職サイト。

今日解いた問題

E - Prefix-free Game

atcoder.jp

実験によって grundy 数を求めるのはよく見る気がする。

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let l: u64 = sc.read();
    let mut trie = Trie {
        nodes: vec![[0; 2]],
    };
    for _ in 0..n {
        let s: Vec<usize> = sc
            .chars()
            .into_iter()
            .map(|c| c as usize - '0' as usize)
            .collect();
        trie.add(&s, 0, 0);
    }

    let mut results = vec![];
    trie.traverse(0, &mut results, l);
    println!(
        "{}",
        if results
            .into_iter()
            .map(|h| 1 << h.trailing_zeros())
            .fold(0, |xor, x| xor ^ x)
            == 0
        {
            "Bob"
        } else {
            "Alice"
        }
    );
}

struct Trie {
    nodes: Vec<[usize; 2]>,
}

impl Trie {
    fn add(&mut self, s: &[usize], pos: usize, cur: usize) {
        if pos == s.len() {
            return;
        }
        if self.nodes[cur][s[pos]] == 0 {
            self.nodes[cur][s[pos]] = self.nodes.len();
            self.nodes.push([0; 2]);
        }
        let cur = self.nodes[cur][s[pos]];
        self.add(s, pos + 1, cur);
    }

    fn traverse(&self, cur: usize, results: &mut Vec<u64>, height: u64) {
        let (a, b) = (self.nodes[cur][0], self.nodes[cur][1]);
        if a == 0 && b == 0 {
            return;
        }
        if a == 0 || b == 0 {
            results.push(height);
        }
        if a != 0 {
            self.traverse(a, results, height - 1);
        }
        if b != 0 {
            self.traverse(b, results, height - 1);
        }
    }
}

fn grundy(l: usize, map: &mut BTreeMap<usize, usize>) -> usize {
    match map.get(&l) {
        Some(&x) => x,
        None => {
            let mut set = BTreeSet::new();
            for i in 1..(l + 1) {
                let mut g = 0;
                for j in 1..i {
                    g ^= grundy(l - j, map);
                }
                set.insert(g);
            }
            let g = (0..).find(|x| !set.contains(x)).unwrap();
            map.insert(l, g);
            g
        }
    }
}

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()
    }
}