AtCoder Regular Contest 108 参加記

# D - AB

D - AB

Cが一見ややこしそうなのでDを見ると、DPで行けそうという第一感を得るので考えてみる。N=1000なのでO(N^2)のDPをやることを考えてみる。

  • i文字目を見ている時に、(最後に見たAの場所, 最後に見たBの場所)をもつといけそう?→無理そう

愚直解を書いて実験してみると、次の3つのみになるということが分かる。

  • 1
  • フィボナッチ数のN項目
  • 2^(N-3)

何もわからないがこれを出力するコードを提出するとAC(48:59)

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();
    let aa = sc.chars()[0];
    let ab = sc.chars()[0];
    let ba = sc.chars()[0];
    let bb = sc.chars()[0];

    let ans = match [aa, ab, ba, bb] {
        ['A', 'A', 'A', 'A'] => 1,
        ['B', 'A', 'A', 'A'] => fib(n),
        ['A', 'B', 'A', 'A'] => pow(n),
        ['B', 'B', 'A', 'A'] => pow(n),
        ['A', 'A', 'B', 'A'] => 1,
        ['B', 'A', 'B', 'A'] => pow(n),
        ['A', 'B', 'B', 'A'] => fib(n),
        ['B', 'B', 'B', 'A'] => fib(n),
        ['A', 'A', 'A', 'B'] => 1,
        ['B', 'A', 'A', 'B'] => fib(n),
        ['A', 'B', 'A', 'B'] => 1,
        ['B', 'B', 'A', 'B'] => 1,
        ['A', 'A', 'B', 'B'] => 1,
        ['B', 'A', 'B', 'B'] => pow(n),
        ['A', 'B', 'B', 'B'] => 1,
        ['B', 'B', 'B', 'B'] => 1,
        _ => unreachable!(),
    };
    println!("{}", ans);

    //
    // for mask in 0..(1 << 5) {
    //     let aa = if mask & (1 << 0) == 0 { 'A' } else { 'B' };
    //     let ab = if mask & (1 << 1) == 0 { 'A' } else { 'B' };
    //     let ba = if mask & (1 << 2) == 0 { 'A' } else { 'B' };
    //     let bb = if mask & (1 << 3) == 0 { 'A' } else { 'B' };
    //
    //     // println!("{:?}", [aa, ab, ba, bb]);
    //
    //     let mut v = vec![vec!['A', 'B']];
    //     for i in 0..10 {
    //         let mut next = vec![];
    //         for t in v {
    //             for i in 1..t.len() {
    //                 let c = match (t[i - 1], t[i]) {
    //                     ('A', 'A') => aa,
    //                     ('A', 'B') => ab,
    //                     ('B', 'A') => ba,
    //                     ('B', 'B') => bb,
    //                     _ => unreachable!(),
    //                 };
    //                 let mut x = t.clone();
    //                 x.insert(i, c);
    //                 next.push(x);
    //             }
    //         }
    //         v = next;
    //         v.sort();
    //         v.dedup();
    //         // println!("n={} {}", i + 3, v.len());
    //     }
    //     println!("{:?} {}", [aa, ab, ba, bb], v.len());
    // }
}

fn fib(n: usize) -> usize {
    let mut prev = [1, 1];
    for _ in 4..=n {
        let next = (prev[0] + prev[1]) % MOD;
        prev = [prev[1], next];
    }
    prev[1]
}
fn pow(n: usize) -> usize {
    if n <= 3 {
        1
    } else {
        let mut res = 1;
        for _ in 0..(n - 3) {
            res = (res * 2) % MOD;
        }
        res
    }
}

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

# C - Keep Graph Connected
C - Keep Graph Connected

  • 何も分からないが、連結になっていれば良いので木を作ることを考える。
  • 「辺の両端の頂点に書き込まれた整数を x,y として、x,y のいずれか一方のみが辺についたラベルと等しい」となっているが、まず「いずれか一方のみ、または両方がラベルと等しい」木を作り、その頂点のラベルを適当に書き換えることで「一方のみ」のグラフにできる。
  • BFS木を作りながら、新たに到達した頂点に、その頂点に到達する際に使った辺のラベルを書き込むと、先ほどの条件を満たすグラフができることに気付く。

これを実装するだけなのだが、バグらせまくって2WAしてAC(83:21 + 2WA)

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

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 graph = vec![vec![]; n];
    for _ in 0..m {
        let u = sc.read::<usize>() - 1;
        let v = sc.read::<usize>() - 1;
        let c: usize = sc.read();
        graph[u].push((v, c));
        graph[v].push((u, c));
    }

    let mut vis = vec![false; n];
    let mut ans = vec![0; n];
    vis[0] = true;
    let mut q = VecDeque::new();
    q.push_back(0);
    let mut used = vec![BTreeSet::new(); n];
    while let Some(v) = q.pop_front() {
        for &(next, label) in graph[v].iter() {
            if vis[next] {
                continue;
            }
            vis[next] = true;
            if ans[v] != label {
                ans[next] = label;
            }
            q.push_back(next);
            used[v].insert(label);
            used[next].insert(label);
        }
    }

    for i in 0..n {
        if ans[i] != 0 {
            continue;
        }
        ans[i] = (1..=n).find(|&x| !used[i].contains(&x)).unwrap();
    }
    for i in 0..n {
        println!("{}", ans[i]);
    }
}
pub struct UnionFind {
    parent: Vec<usize>,
    sizes: Vec<usize>,
    size: usize,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        UnionFind {
            parent: (0..n).map(|i| i).collect::<Vec<usize>>(),
            sizes: vec![1; n],
            size: n,
        }
    }

    pub fn find(&mut self, x: usize) -> usize {
        if x == self.parent[x] {
            x
        } else {
            let px = self.parent[x];
            self.parent[x] = self.find(px);
            self.parent[x]
        }
    }

    pub fn unite(&mut self, x: usize, y: usize) -> bool {
        let parent_x = self.find(x);
        let parent_y = self.find(y);
        if parent_x == parent_y {
            return false;
        }

        let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] {
            (parent_y, parent_x)
        } else {
            (parent_x, parent_y)
        };

        self.parent[small] = large;
        self.sizes[large] += self.sizes[small];
        self.sizes[small] = 0;
        self.size -= 1;
        true
    }
}

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

# 結果

  • 赤パフォ: ABCDE 94:10
  • 橙パフォ: ABCD 61:21
  • 2128: ABCD93:21

# 感想

  • Dで速やかに実験に移行できたのは良かった(運も良かった)。
  • Cでバグらせまくったのは良くなかった。特に、気づいていたケースをケアし忘れていたので、実装前に気づいた注意すべきことを提出前に確認できるように、リストアップしておいたほうが良いかもしれない。

ISUCON10参加記

ISUCON10に garasubo さんと GolDDranks さんとチーム「勉強不足の分は有り余る才能でカバーでカバーしようかなと思っております」で参加して予選通過しました。チーム名がtypoしているのですが、一度登録すると修正できない仕様なので、カバーでカバーするしかない。

今回は完全オンラインでボイスチャットも使っておらず、全てログが残っていたので、時系列でまとめてみようと思います。

前日まで

使用言語をRustにすることでチームが決まりました。ISUCON9を使って2回くらい練習しましたが、ISUCON9まではRust参考実装がないので、ひたすら移植ゲーになりました。移植ゲーの中でactix-webの使い方を覚え、ついでにnginxとalpの使い方も覚えました。練習を通して、サーバー上でRustアプリケーションをコンパイルするのではなく、ローカルでコンパイルした実行可能ファイルをrsyncでサーバーに転送するデプロイ方法が確立されました。

当日

10:00-

開始が後ろ倒しになり、せっかく空いたので直前に何か準備しようと思いつつ Splatoon を始めたら一瞬で開始時刻になりました。任天堂すごい。

12:20-

  • サーバー上のソースコードgithubに書き出す。
  • garasuboがnginxのログ設定を整える。
  • とりあえずgolangを落としてrustを立ち上げてベンチマークを走らせる。537点。
  • GolDDranks がボット対策を始める。
  • 僕がmain.rs をエンドポイントごとに分割し始める。
  • garasubo がindexを貼ったりする。
  • とりあえずserver1をapp、server2をmysqlという構成でやってみることにする。

15:00-

  • GolDDranksのbot対策はあまり効かなかったらしい。
  • main.rsの分割が終わったのでsearch_estate_nazotteを見てみる。SQLで点が凸法の内部にあるかどうかを判定しているが、幾何ライブラリを貼って全部ローカルで計算するようにする。638点。

16:00-

  • garasuboがindexを貼る。721点。
  • GolDDranksがメモリキャッシュをやり始める。
  • garasuboがmysqlサーバーの負荷分散のためにchairとestateをそれぞれ別のサーバーで管理する実装を開始。
  • 僕がestateを全部メモリに載せる実装を開始。

17:00-

  • GolDDranksのメモリキャッシュが完成する。static な AtomicPtr があるなど勢いがある。1040点。
  • 僕がrecommend でSQLを叩かずにオンメモリのestateから結果を返すようにする。1105点。

18:00-

  • garasuboの2台mysql実装が完成する。1775点。
  • garasuboがクエリキャッシュを有効にする。2465点。

19:00-

  • 高負荷に耐えられるようになったのでランダムにメモリキャッシュが壊れるようになる。
  • 僕は用事があるのでここで離脱。

20:00-

このあとgarasuboがindexを貼って3084点を出したりしたらしいですが、ベンチマークガチャを回して2684点で終了したらしいです。

感想

  • シンプルな仕様でありながら面白い問題だったと思います。作問者はすごい。
  • Rustの参考実装もシンプルで素直な実装になっていて、大変取り組みやすかったです。
  • コンテストを突然延期したりコンテスト中は順位表やベンチマーカーが壊れていたりして競技の体をなしていなかったのは、少しもったいないと思いました。
  • 参加者用のインフラは非常に安定していて、問題に集中することができました。
  • 本戦もがんばります。

ICFPC 反省メモ

ICFPC 2020 に参加してかなり楽しめた。来年も参加したいと思うので、1年後の自分に向けてメモを残す。

  • インフラ班は3日目には何もしないのが理想。48時間コンテストと思っておくと良さそう。むしろ事前準備をきっちりしておくのが大事で準備に3日くらいかけても良いと思う。
  • 短時間コンテストでも設計は大事。このあたり osa_k さんは天才。
  • シミュレーターや自己対戦インフラはデバッグや動作確認のためにも不可欠。大抵のICFPCではルールが異常に複雑だったり不明確だったりで公式提供のツールに任せたくなるが、そこを逃げない胆力が大事。
  • ツール類は各自の手元で動かせるものが最強。ウェブサービスにこだわる必要はない。今回で言うと処理系はウェブサービスであっても良いが、手元で動かせればベストだった。
  • ↑を達成するために、各自の環境を最低限揃えておく必要がある。例えば Docker の動作確認とかは直前の2時間とかでできたはず。

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