Ubuntu インストール時設定メモ

ターミナルの設定

  • byobuをインストール
  • Gnome Terminal のカスタムコマンドを byobu にする
  • ~/.byobu/.tmux.conf に set-option -g mouse on を書く
  • cargo install skim して .bashrc に source $HOME/.cargo/registry/src/github.com-1ecc6299db9ec823/skim-0.8.1/shell/key-bindings.bash を書く。これで skim が ctrl-r で動くようになる。

CapsLock 潰し

  • gnome-tweak-tools をインストール
  • Keyboard & Mouse > Additional Layout Options > Caps Lock behaviour から設定

AtCoder Problems 開発を始めよう!

AtCoder Problems 開発を始めよう!

必要なもの

始める前に下記のツールが必要です。インストールしておきましょう。

開発環境をセットアップする

# リポジトリを clone する
git clone git@github.com:kenkoooo/AtCoderProblems.git

# atcoder-problems-frontend ディレクトリに移動する
cd ./AtCoderProblems/atcoder-problems-frontend/

# 必要なパッケージをインストールしてくれる魔法のコマンド
yarn

# ローカルサーバーを起動する
yarn start

ここまでやると http://localhost:3000/ にアクセスして自分の PC で起動している AtCoder Problems を確認できます。ソースコードを編集・保存すると自動的にコンパイルされて変更が反映されます。

試しに ./src/components/NavigationBar.tsx を開いて以下の箇所を AtCoder Problems2 に変更してみましょう。

f:id:kenkoooo:20200612141112p:plain

保存してブラウザで確認すると以下のように更新されていると思います。

f:id:kenkoooo:20200612141204p:plain

いかがでしたか?

AGC045 A - Xor Battle

atcoder.jp

「ある正の整数の集合 A から好きなものを選んで XOR をとり、Kを作ることができるか?」という問題を解く。この問題は集合から作りうる数を全て列挙するのではなく、集合の基底をとり、そこから K が作れるかを考えれば良い。

基底は以下のようにして作れる。

let mut base = vec![];
for i in (0..n) {
    let mut a = a[i];
    for &b in base.iter() {
        if a ^ b < a {
            a ^= b;
        }
    }
    if a != 0 {
        base.push(a);
    }
}

sugoi

AtCoder Beginner Contest 168 F - . (Single Dot)

問題

atcoder.jp

解法

まずはサイズの小さい問題を考える。入力として与えられる全ての線分の座標 (x, y) が 0<=x,y<=1000 を満たすとすると、max(x) * max(y) の 2 次元配列を持って、その上で幅優先探索などをして、線分をまたがずに到達できるマスの数を数えれば良いことになる。マス (i, j) は直線 x=i, x=i+1, y=j, y=j+1 に囲まれたマスを表すとする。(i, j) と (i, j+1) の間に線分があるかどうかは、y=j+1 で x1<=j&&j+1<=x2 を満たす線分が存在するかどうかを調べれば良い。これは、線分を y 座標ごとにまとめて、(x1,x2) をソートしておくと二分探索で j<=x1 を満たす線分とその1つ前の線分を取り出して調べることで判定できる。これで隣接するセルに移動できるかどうかが判定できるようになった。よって問題は、(0, 0) を出発して、線分をまたがずに隣接するセルを渡り歩き、到達したセルの数を数えれば良い。

実際の問題を考える。線分の座標の範囲は広いが、値として現れる個数は高々 N 個なので、座標圧縮して後で戻すことにする。この時、セル (i,j) の面積は (x[i+1]-x[i]) * (y[i+1]-y[i]) で求められるので、最後の復元も簡単にできる。無限に行くことができるので、x=-INF, x=INF, y=-INF, y=INF の直線が存在して、この直線のところまで来たら INF を出力することにする。これは実装上では i=0 などのセルに到達できれば INF を出力すれば良い。

コード

use std::collections::VecDeque;

const INF: i64 = 1 << 50;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let m: usize = sc.read();

    let mut vx = vec![-INF, 0, INF];
    let mut vy = vec![-INF, 0, INF];

    let mut x_lines = vec![];
    for _ in 0..n {
        let x1: i64 = sc.read();
        let x2: i64 = sc.read();
        let y: i64 = sc.read();
        x_lines.push((x1, x2, y));
        vx.push(x1);
        vx.push(x2);
        vy.push(y);
    }

    let mut y_lines = vec![];
    for _ in 0..m {
        let x: i64 = sc.read();
        let y1: i64 = sc.read();
        let y2: i64 = sc.read();
        y_lines.push((y1, y2, x));
        vy.push(y1);
        vy.push(y2);
        vx.push(x);
    }

    vx.sort();
    vx.dedup();
    vy.sort();
    vy.dedup();

    let h = vx.len();
    let w = vy.len();

    let mut x_wall = vec![vec![]; w];
    for &(x1, x2, y) in x_lines.iter() {
        let x1 = vx.binary_search(&x1).unwrap();
        let x2 = vx.binary_search(&x2).unwrap();
        let y = vy.binary_search(&y).unwrap();
        x_wall[y].push((x1, x2));
    }

    for x_wall in x_wall.iter_mut() {
        x_wall.sort();
    }

    let mut y_wall = vec![vec![]; h];
    for &(y1, y2, x) in y_lines.iter() {
        let y1 = vy.binary_search(&y1).unwrap();
        let y2 = vy.binary_search(&y2).unwrap();
        let x = vx.binary_search(&x).unwrap();
        y_wall[x].push((y1, y2));
    }

    for y_wall in y_wall.iter_mut() {
        y_wall.sort();
    }

    let mut board = vec![vec![false; w - 1]; h - 1];

    let si = vx.binary_search(&0).unwrap();
    let sj = vy.binary_search(&0).unwrap();
    board[si][sj] = true;
    let mut queue = VecDeque::new();
    queue.push_back((si, sj));
    while let Some((x, y)) = queue.pop_front() {
        if x > 0 {
            let conflict = wall(&y_wall[x], y);
            if !board[x - 1][y] && !conflict {
                board[x - 1][y] = true;
                queue.push_back((x - 1, y));
            }
        }

        if x + 1 < board.len() {
            let conflict = wall(&y_wall[x + 1], y);
            if !board[x + 1][y] && !conflict {
                board[x + 1][y] = true;
                queue.push_back((x + 1, y));
            }
        }

        if y > 0 {
            let conflict = wall(&x_wall[y], x);
            if !board[x][y - 1] && !conflict {
                board[x][y - 1] = true;
                queue.push_back((x, y - 1));
            }
        }

        if y + 1 < board[x].len() {
            let conflict = wall(&x_wall[y + 1], x);
            if !board[x][y + 1] && !conflict {
                board[x][y + 1] = true;
                queue.push_back((x, y + 1));
            }
        }
    }

    let mut ans = 0;
    for x in 0..board.len() {
        for y in 0..board[x].len() {
            if !board[x][y] {
                continue;
            }

            if x == 0 || x == board.len() - 1 || y == 0 || y == board[x].len() - 1 {
                println!("INF");
                return;
            }

            let x1 = vx[x];
            let x2 = vx[x + 1];
            let y1 = vy[y];
            let y2 = vy[y + 1];
            ans += (x2 - x1) * (y2 - y1);
        }
    }

    println!("{}", ans);
}

fn wall(walls: &Vec<(usize, usize)>, x: usize) -> bool {
    let mut conflict = false;
    let right = walls.binary_search(&(x, 0)).err().unwrap();
    if walls.len() > right {
        let (x1, x2) = walls[right];
        if x1 <= x && x + 1 <= x2 {
            conflict = true;
        }
    }

    if right > 0 && walls.len() > right - 1 {
        let (x1, x2) = walls[right - 1];
        if x1 <= x && x + 1 <= x2 {
            conflict = true;
        }
    }
    conflict
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .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 Grand Contest 038 C - LCMs

問題

atcoder.jp

解法メモ

 \rm lcm(A_i, A_j) を求めるのではなく \frac{A_i A_j}{\rm gcd(A_i,A_j)} を求めていく方針を考える。

サンプル2の以下の例を解くことを考える。

8
1 2 3 4 6 8 12 12
 \sum _{ i \lt j } A_i A_j = (\sum_{i} A_i )^2 - \sum_{i} A_i^2

なので、i j のペアについて考えるのではなく単体で考えてあとで調整できるということを頭に留めておく。

最大公約数ごとにグルーピングしたりしたいが、とりあえずそのあたりは大変そうなので、まずは約数ごとにまとめて眺めてみる。

1 => {1, 2, 3, 4, 6, 8, 12, 12}
2 => {2, 4, 6, 8, 12, 12}
3 => {3, 6, 12, 12}
4 => {4, 8, 12, 12}
6 => {6, 12, 12}
8 => {8}
12 => {12, 12}

これについて、最大公約数はとりあえず置いておいて、約数で割って計算するとどうなるか見てみる。

 \frac{12 \times 12}{12} + \frac{12 \times 12 + 12 \times 6 + 12 \times 6}{6} + ...

という感じになる。この部分で、 \frac{12 \times 12}{12} + \frac{12 \times 6 + 12 \times 6}{6} + ...は最終的な回答に含まれるが、 \frac{12 \times 12}{6} は含まれないので取り除かなければならない。

なので、最終的な答えについて考えてみると

 \frac{12 \times 12}{12} + \frac{12 \times 12 + 12 \times 6 + 12 \times 6}{6} + ...  - \frac{12 \times 12}{6} - \frac{12 \times 12}{4} - \frac{12 \times 12}{3} - \frac{12 \times 12}{2} - \frac{12 \times 12}{1}

という感じになる。

コード

use self::mod_int::ModInt;
const MOD: usize = 998244353;
const N: usize = 1000001;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let mut divisors = vec![vec![]; N];
    for i in 1..N {
        let mut cur = i;
        while cur < N {
            divisors[cur].push(i);
            cur += i;
        }
    }

    let mut inv = vec![ModInt(1); N];
    for i in 1..N {
        inv[i] /= i;
    }

    let n: usize = sc.read();
    let mut count = vec![0; N];
    for _ in 0..n {
        let a: usize = sc.read();
        count[a] += 1;
    }

    let mut sum = vec![ModInt(0); N];
    let mut sq_sum = vec![ModInt(0); N];
    for i in 0..N {
        if count[i] == 0 {
            continue;
        }

        let count = count[i];
        for &divisor in divisors[i].iter() {
            sum[divisor] += ModInt(i) * count;
            sq_sum[divisor] += ModInt(i) * i * count;
        }
    }

    let mut sum_by_d = vec![ModInt(0); N];
    for d in (1..N).rev() {
        sum_by_d[d] += (sum[d] * sum[d] - sq_sum[d]) * inv[2] * inv[d];
        for &divisor in divisors[d].iter() {
            if d == divisor {
                continue;
            }
            let sum_by_d_d = sum_by_d[d];
            sum_by_d[divisor] -= sum_by_d_d * d * inv[divisor];
        }
    }

    let mut ans = ModInt(0);
    for d in 1..N {
        ans += sum_by_d[d];
    }

    println!("{}", ans.0);
}

pub mod mod_int {
    use super::MOD;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    type Num = usize;

    #[derive(Clone, Copy)]
    pub struct ModInt<T: Copy + Clone>(pub T);

    impl Add<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self + rhs.0
        }
    }

    impl Add<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let mut t = rhs + self.0;
            if t >= MOD {
                t = t - MOD;
            }
            ModInt(t)
        }
    }

    impl Sub<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: Num) -> ModInt<Num> {
            let rhs = if rhs >= MOD { rhs % MOD } else { rhs };
            let value = if self.0 < rhs { self.0 + MOD } else { self.0 };
            ModInt(value - rhs)
        }
    }

    impl Sub<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self - rhs.0
        }
    }

    impl AddAssign<Num> for ModInt<Num> {
        fn add_assign(&mut self, other: Num) {
            *self = *self + other;
        }
    }
    impl AddAssign<ModInt<Num>> for ModInt<Num> {
        fn add_assign(&mut self, other: ModInt<Num>) {
            *self = *self + other;
        }
    }

    impl SubAssign<Num> for ModInt<Num> {
        fn sub_assign(&mut self, other: Num) {
            *self = *self - other;
        }
    }

    impl SubAssign<ModInt<Num>> for ModInt<Num> {
        fn sub_assign(&mut self, other: ModInt<Num>) {
            *self = *self - other;
        }
    }

    impl Div<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            self * ModInt(rhs).pow(MOD - 2)
        }
    }

    impl Div<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self / rhs.0
        }
    }

    impl DivAssign<Num> for ModInt<Num> {
        fn div_assign(&mut self, rhs: Num) {
            *self = *self / rhs
        }
    }
    impl DivAssign<ModInt<Num>> for ModInt<Num> {
        fn div_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self / rhs
        }
    }

    impl Mul<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self * rhs.0
        }
    }
    impl Mul<Num> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let t = (self.0 * rhs) % MOD;
            ModInt(t)
        }
    }

    impl MulAssign<Num> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: Num) {
            *self = *self * rhs;
        }
    }

    impl MulAssign<ModInt<Num>> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<Num> {
        pub fn pow(self, e: Num) -> ModInt<Num> {
            let mut result = ModInt(1);
            let mut cur = self;
            let mut e = e;
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                }
                e >>= 1;
                cur *= cur;
            }
            result
        }
    }
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .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 Regular Contest 071 F - Infinite Sequence

問題

rated 黄色 diff 最後の生き残り

F - Infinite Sequence

解法

1より大きい数が連続すると以降は全て決まるので、

  • (1)(211)(3111)(41111)... から構成される prefix

  • a>1 かつ b>1 として abbbbbb... となる suffix
  • a>1として a11111.... となる suffix

のいずれかの suffix を組み合わせて作る。

dp[i] := 先頭の i 要素を (1)(211)(3111)... から構成する組み合わせの数とすると dp[i] = dp[i-1] + dp[i-3] + dp[i-4] + ... + dp[0] であることが分かるので、dp[i] が求まる。

(1)(211)(3111)(41111)... から構成される prefix と a>1 かつ b>1 として abbbbbb... となる suffix の組み合わせの数は

    for i in 0..(n - 1) {
        ans += dp[i] * (n - 1) * (n - 1);
    }

で求めている。

また、n-1項を(1)(211)(3111)(41111)... から構成し、n項目を好きに選んで無限に繰り返すのはdp[n - 1] * nとなる。これを (1) とする。

最初の k 要素を(1)(211)(3111)(41111)... から構成し、その次の要素を a>1 とし、それ以降を 1111... とするような数列を求めたいが、(1)で選んだものは取り除きたい。その場合、先頭k要素と次のaとそれに続くa個の1を合わせた k+1+a 要素がn個以上になっていなければならない(n-1個以下の場合、dp[k+1+a]に含まれているため)し、kかつk<=n-2でなければならない(k=n-1はdp[n-1]*nに含まれているため)。

よって k+1+a>=n かつ k<=n-2かつa>1なので、n >= a > max(n-k-2,1) より、kを決めた時に a として選べるものはmin(k+2, n-1)個である。よってこの場合の組み合わせは

    for k in 0..(n - 1) {
        ans += dp[k] * min(k + 2, n - 1);
    }

で求まる。

コード

use self::mod_int::ModInt;
use std::cmp::min;

const MOD: usize = 1e9 as usize + 7;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    if n == 1 {
        println!("1");
        return;
    }

    let mut dp = vec![ModInt(0); n];
    dp[0] = ModInt(1);
    dp[1] = ModInt(1);

    let mut sum = vec![ModInt(0); n + 1];
    sum[1] = dp[0];
    sum[2] = dp[1] + sum[1];
    for i in 2..n {
        dp[i] = dp[i - 1] + sum[i - 2];
        sum[i + 1] = sum[i] + dp[i];
    }

    let mut ans = ModInt(0);
    for i in 0..(n - 1) {
        ans += dp[i] * (n - 1) * (n - 1);
    }
    ans += dp[n - 1] * n;
    for k in 0..(n - 1) {
        ans += dp[k] * min(k + 2, n - 1);
    }
    println!("{}", ans.0);
}

pub mod mod_int {
    use super::MOD;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    type Num = usize;

    #[derive(Clone, Copy)]
    pub struct ModInt<T: Copy + Clone>(pub T);

    impl Add<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self + rhs.0
        }
    }

    impl Add<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let mut t = rhs + self.0;
            if t >= MOD {
                t = t - MOD;
            }
            ModInt(t)
        }
    }

    impl Sub<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: Num) -> ModInt<Num> {
            let rhs = if rhs >= MOD { rhs % MOD } else { rhs };
            let value = if self.0 < rhs { self.0 + MOD } else { self.0 };
            ModInt(value - rhs)
        }
    }

    impl Sub<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self - rhs.0
        }
    }

    impl AddAssign<Num> for ModInt<Num> {
        fn add_assign(&mut self, other: Num) {
            *self = *self + other;
        }
    }
    impl AddAssign<ModInt<Num>> for ModInt<Num> {
        fn add_assign(&mut self, other: ModInt<Num>) {
            *self = *self + other;
        }
    }

    impl SubAssign<Num> for ModInt<Num> {
        fn sub_assign(&mut self, other: Num) {
            *self = *self - other;
        }
    }

    impl SubAssign<ModInt<Num>> for ModInt<Num> {
        fn sub_assign(&mut self, other: ModInt<Num>) {
            *self = *self - other;
        }
    }

    impl Div<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            self * ModInt(rhs).pow(MOD - 2)
        }
    }

    impl Div<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self / rhs.0
        }
    }

    impl DivAssign<Num> for ModInt<Num> {
        fn div_assign(&mut self, rhs: Num) {
            *self = *self / rhs
        }
    }
    impl DivAssign<ModInt<Num>> for ModInt<Num> {
        fn div_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self / rhs
        }
    }

    impl Mul<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self * rhs.0
        }
    }
    impl Mul<Num> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let t = (self.0 * rhs) % MOD;
            ModInt(t)
        }
    }

    impl MulAssign<Num> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: Num) {
            *self = *self * rhs;
        }
    }

    impl MulAssign<ModInt<Num>> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<Num> {
        pub fn pow(self, e: usize) -> ModInt<Num> {
            let mut result = ModInt(1);
            let mut cur = self;
            let mut e = e;
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                }
                e >>= 1;
                cur *= cur;
            }
            result
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .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()
    }
}

Javaが遅いって お前それPetrの前でも同じ事言えんの?

うっかり「Javaは遅いので競技プログラミングには向いていない」みたいなことを言ってしまう人が稀にいますが、世界最強の一角であるところのPetrさんはJavaで問題を解きまくっているわけです。

       _,,;' '" '' ゛''" ゛' ';;,,
      (rヽ,;''"""''゛゛゛'';, ノr)   Javaが遅いって
      ,;'゛ i _  、_ iヽ゛';,    お前それPetrの前でも同じ事言えんの?
      ,;'" ''| ヽ・〉 〈・ノ |゙゛ `';,
      ,;'' "|   ▼   |゙゛ `';,
      ,;''  ヽ_人_ /  ,;'_
     /シ、  ヽ⌒⌒ /   リ \
    |   "r,, `"'''゙´  ,,ミ゛   |
    |      リ、    ,リ    |
    |   i   ゛r、ノ,,r" i   _|
    |   `ー――----┴ ⌒´ )
    (ヽ  ______ ,, _´)
     (_⌒ ______ ,, ィ
      丁           |
       |           |

ところで「自分の好きな言語は競技プログラミングには向いていないかもしれない…」という不安に駆られた時、誰を思い浮かべればよいのでしょうか?Javaの時はPetrを思い浮かべればいいとして、その他の言語の場合は?

あるユーザーがAtCoderで最も多くの問題をACしている言語を、そのユーザーのメイン言語とします。メイン言語ごとにユーザーをグループ分けして、グループ内でMax Ratingが最高のユーザーを抽出しました。

言語 ユーザー Max Rating
C sheyasutaka 2686
C# chokudai 3056
C++ tourist 4208
Crystal tomerun 2884
D hos_lyric 3135
Haskell tos 2544
Java Petr 3882
Nim chaemon 2231
Perl x20 2028
PyPy Tallfall 2107
Python maspy 2587
Ruby betrue12 2553
Rust ichyo 2528

いかがでしたか?C++が遅いと感じた時はtouristさんに相談すると良さそうですね!

コード

use scraper::{Html, Selector};
use serde::Deserialize;
use std::collections::BTreeMap;

#[derive(Deserialize)]
struct LanguageEntry {
    user_id: String,
    language: String,
    count: usize,
}

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let client = reqwest::ClientBuilder::new().gzip(true).build().unwrap();

    let lang: Vec<LanguageEntry> = client
        .get("https://kenkoooo.com/atcoder/resources/lang.json")
        .send()
        .await?
        .json()
        .await?;

    let mut map = BTreeMap::new();
    for e in lang.into_iter() {
        let cur = map.entry(e.user_id).or_insert_with(|| (String::new(), 0));
        if cur.1 < e.count {
            *cur = (e.language, e.count);
        }
    }

    let mut language2user = BTreeMap::new();

    let table_selector = Selector::parse("div.table-responsive").unwrap();
    let tbody_selector = Selector::parse("tbody").unwrap();
    let span_selector = Selector::parse("span").unwrap();
    let tr_selector = Selector::parse("tr").unwrap();

    for i in 0..10 {
        let html = client
            .get(&format!("https://atcoder.jp/ranking?page={}", i + 1))
            .send()
            .await?
            .text()
            .await?;
        let document = Html::parse_document(&html);
        let table = document.select(&table_selector).next().unwrap();
        let tbody = table.select(&tbody_selector).next().unwrap();

        for tr in tbody.select(&tr_selector) {
            let tds = tr
                .select(&Selector::parse("td").unwrap())
                .collect::<Vec<_>>();
            let user_id = tds[1]
                .select(&span_selector)
                .next()
                .unwrap()
                .text()
                .next()
                .unwrap();
            let max_rating: u32 = tds[4].text().next().unwrap().parse().unwrap();

            if let Some(e) = map.get(user_id) {
                if !language2user.contains_key(&e.0) {
                    language2user.insert(e.0.clone(), (user_id.to_string(), max_rating));
                }
            }
        }
    }

    for (language, (user_id, max_rating)) in language2user.into_iter() {
        println!("|{}|{}|{}|", language, user_id, max_rating);
    }

    Ok(())
}