SoundHound Inc. Programming Contest 2018 (春) D - 建物

問題

D - 建物

解法

(i, j) から (i, k) に移動して (i+1, k) に移動する経路 (i, j) => (i+1, k) を考える。このとき、 (i, j-1) => (i+1, k) よりも多くの報酬が得られることに留意する。次に (i+1, k+1) に移動する経路を考える。このとき (i, j-1) => (i+1, k+1) よりも (i, j) => (i+1, k+1) の方がより多くの報酬が得られる。このように、下の階から上の階へ上がる経路はしゃくとり法によって求まる。

コード

use std::cmp;
use std::i64::MIN;

fn main() {
    let (h, w) = {
        let v = read_values::<usize>();
        (v[0], v[1])
    };

    let p = {
        let mut p = vec![vec![0; w]; h + 1];
        for i in 0..h {
            let v = read_values::<i64>();
            for j in 0..w {
                p[i][j] = v[j];
            }
        }
        p
    };

    let f = {
        let mut f = vec![vec![0; w]; h + 1];
        for i in 0..h {
            let v = read_values::<i64>();
            for j in 0..w {
                f[i][j] = v[j];
            }
        }
        f
    };

    let mut gain = vec![vec![MIN; w]; h + 1];
    gain[0][0] = p[0][0];

    for i in 0..h {
        let mut left_turn = vec![0; w];
        for j in 1..w {
            left_turn[j] = cmp::max(left_turn[j - 1] + p[i][j - 1] - (f[i][j - 1] + f[i][j]), 0);
        }
        let mut right_turn = vec![0; w];
        for j in (0..(w - 1)).rev() {
            right_turn[j] = cmp::max(right_turn[j + 1] + p[i][j + 1] - (f[i][j + 1] + f[i][j]), 0);
        }

        let mut sum = vec![0; w + 1];
        for j in 0..w {
            sum[j + 1] = sum[j] + p[i][j] - f[i][j];
        }

        if i == 0 {
            for j in 0..w {
                gain[i + 1][j] = p[i + 1][j] - f[i + 1][j] + sum[j + 1] + right_turn[j];
            }
        } else {
            let mut left_max = 0;
            for j in 0..w {
                let segment_sum = sum[j + 1] - sum[left_max + 1];
                let enter_gain = p[i + 1][j] - f[i + 1][j];

                let old_gain = gain[i][left_max] + segment_sum + left_turn[left_max];
                let new_gain = gain[i][j] + left_turn[j];
                if old_gain < new_gain {
                    left_max = j;
                }

                gain[i + 1][j] = cmp::max(old_gain, new_gain) + right_turn[j] + enter_gain;
            }

            let mut right_max = w - 1;
            for j in (0..w).rev() {
                let segment_sum = sum[right_max] - sum[j];
                let enter_gain = p[i + 1][j] - f[i + 1][j];

                let old_gain = gain[i][right_max] + segment_sum + right_turn[right_max];
                let new_gain = gain[i][j] + right_turn[j];
                if old_gain < new_gain {
                    right_max = j;
                }

                gain[i + 1][j] = cmp::max(
                    cmp::max(old_gain, new_gain) + left_turn[j] + enter_gain,
                    gain[i + 1][j],
                );
            }
        }
    }
    for i in 0..w {
        println!("{}", gain[h][i]);
    }
}


fn read_line() -> String {
    let stdin = std::io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T>
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
{
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

SoundHound Inc. Programming Contest 2018 (春) C - 広告

問題

C: 広告 - SoundHound Inc. Programming Contest 2018 (春) | AtCoder

解法

グリッドグラフでの最大安定集合を求めたい。最大安定集合は最小点被覆の補集合なので、最小点被覆問題を解く。二部グラフでは最小点被覆問題は最大マッチング問題の双対なので（未証明）、最大マッチング問題を解く。

コード

use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;

fn main() {
    let (r, c) = {
        let v = read_values::<usize>();
        (v[0], v[1])
    };

    let dot = ".".as_bytes()[0];
    let map = (0..r).map(|_| {
        read_line()
            .trim()
            .bytes()
            .map(|b| b == dot)
            .collect::<Vec<_>>()
    }).collect::<Vec<_>>();

    let mut ok = 0;

    let mut dinitz = Dinitz::new(r * c + 2);
    let source = r * c;
    let sink = source + 1;
    for i in 0..r {
        for j in 0..c {
            if !map[i][j] { continue; }

            ok += 1;

            let v = i * c + j;
            if i % 2 == j % 2 {
                dinitz.add_edge(source, v, 1);
            } else {
                dinitz.add_edge(v, sink, 1);
                continue;
            }

            let x = vec![(1, 0), (-1, 0), (0, 1), (0, -1)];
            for t in &x {
                let (di, dj) = *t;
                let ni = (i as i32) + di;
                let nj = (j as i32) + dj;
                if ni < 0 || ni >= r as i32 || nj < 0 || nj >= c as i32 {
                    continue;
                }
                let w = ni * (c as i32) + nj;
                dinitz.add_edge(v, w as usize, 1);
            }
        }
    }

    let f = dinitz.max_flow(source, sink);
    println!("{}", ok - f as usize);
}

struct Edge {
    pub to: usize,
    pub rev: usize,
    pub cap: i64,
}

pub struct Dinitz {
    g: Vec<Vec<Edge>>,
    level: Vec<i32>,
    iter: Vec<usize>,
}

impl Dinitz {
    pub fn new(v: usize) -> Dinitz {
        let mut g: Vec<Vec<Edge>> = Vec::new();
        for _ in 0..v {
            g.push(Vec::new());
        }
        Dinitz {
            g: g,
            level: vec![0; v],
            iter: vec![0; v],
        }
    }

    pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
        let to_len = self.g[to].len();
        let from_len = self.g[from].len();
        self.g[from].push(Edge {
            to: to,
            rev: to_len,
            cap: cap,
        });
        self.g[to].push(Edge {
            to: from,
            rev: from_len,
            cap: 0,
        });
    }

    fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
        if v == t {
            return f;
        }
        while self.iter[v] < self.g[v].len() {
            let (e_cap, e_to, e_rev);
            {
                let ref e = self.g[v][self.iter[v]];
                e_cap = e.cap;
                e_to = e.to;
                e_rev = e.rev;
            }
            if e_cap > 0 && self.level[v] < self.level[e_to] {
                let d = self.dfs(e_to, t, cmp::min(f, e_cap));
                if d > 0 {
                    {
                        let ref mut e = self.g[v][self.iter[v]];
                        e.cap -= d;
                    }
                    {
                        let ref mut rev_edge = self.g[e_to][e_rev];
                        rev_edge.cap += d;
                    }
                    return d;
                }
            }
            self.iter[v] += 1;
        }

        return 0;
    }

    fn bfs(&mut self, s: usize) {
        let v = self.level.len();
        self.level = vec![-1; v];
        self.level[s] = 0;
        let mut deque = VecDeque::new();
        deque.push_back(s);
        while !deque.is_empty() {
            let v = deque.pop_front().unwrap();
            for e in &self.g[v] {
                if e.cap > 0 && self.level[e.to] < 0 {
                    self.level[e.to] = self.level[v] + 1;
                    deque.push_back(e.to);
                }
            }
        }
    }

    pub fn max_flow(&mut self, s: usize, t: usize) -> i64 {
        let v = self.level.len();
        let mut flow: i64 = 0;
        loop {
            self.bfs(s);
            if self.level[t] < 0 {
                return flow;
            }
            self.iter = vec![0; v];
            loop {
                let f = self.dfs(s, t, MAX);
                if f == 0 {
                    break;
                }
                flow += f;
            }
        }
    }
}

fn read_line() -> String {
    let stdin = std::io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, {
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

LG Gram 14Z970-GA55J レビュー

LG Gram 買いました

会社の MacBook Pro 2015 13-inch を使っていましたが、会社をやめるにあたって自分用の PC を買いました。かなり悩んだ末買いましたが思ったより良かったのでレビューを書いておきます。

商品リンク

http://amzn.to/2Csklt8

購入の際の検討事項

以下の条件でノート PC を探していました。

• 日本で買えるもの（海外から取り寄せると初期不良とかあった時に面倒くさそう）
• メモリ 16 GB
• 英字配列キーボード
• 重量 1 kg 以下
• 13 インチ以上
• 10 万円前後

この条件に合致するものはなく、近いものとして以下のものがありました。

• ThinkPad
  • 英字配列のものは 20 万円くらいする
• Dell XPS
  • メモリ 16 GB のものは 20 万円くらいする
• LG Gram
  • メモリ 16 GB のモデルはないが、自分で増設できるタイプ

画面

14 インチのものを買いました。前の MacBook Pro が 13 インチだったので同じで良いかと思いましたが、LG Gram は画面の端が薄いのらしく、 14 インチ版が MacBook Pro 13 インチ版と同じ大きさらしかったので、14 インチに決めました。Retina ディスプレイを長きに渡って使ってきたので画面の粗さが気になると思って悩みましたが、意外にも全く気になりませんでした。

キーボード

英字配列が欲しかったので、英字配列しか存在しない Gram を選んで良かったです。購入の候補には ThinkPad も入っていたのですが、これは日本では JIS キーボードのものしか買えないとのことだったので諦めました。

メモリ

16 GB メモリを積んでいるものが欲しかったのですが、存在しなかったため、後から 16 GB に増設できる（LG で増設してもらうこともできますし、保証対象外ですが自分で増設することも出来ます）8GB モデルを選びました。Mac では 16 GB 無いと話にならなかったのですが、これは OS X がメモリをバカ食いするだけで、 Ubuntu をインストールして使う分には 8 GB で全く問題ありませんでした。

CPU

Core i5-7200U で 2 コア 4 スレッドです。動画のエンコードなどもそこそこ出来る性能です。 Scala のビルドも十分な速度で出来るので満足しています。

タッチパッド

MacBook Pro と違って、クリックがソフトウェアではなく物理なので、Mac に慣れていると少し違和感はあります。2本指での操作にも対応しています。

バッテリー

主な用途がプログラミングなのですが、この用途だと6〜8時間ほど使えます。

重量

971gだそうです。個人的にはかなり軽く感じます。肩掛けバッグに入れても気にならない程度の軽さです。

値段

14 万円くらいしました。ちょっと高い・・・

おわりに

それなりに良い買い物をしたと思います。特に Ubuntu との相性が良いのが気に入っています。

並列二分探索（解説なしバージョン）

adventar.org

並列二分探索、名前からして難しそうな感じがしていたが、特に難しいわけではなかった。

並列二分探索

個人的には並列という名前は正しくない気がします。

普通の二分探索は次の通り。

let mut ng = 0;
let mut ok = m;
for _ in 0..30 {
    let med = (ng + ok) / 2;
    // 何かしらの操作
    if (何かしらの条件) {
        ok = med;
    } else {
        ng = med;
    }
}

並列二分探索は次の通り。

let mut ng = vec![0; q];
let mut ok = vec![m; q];

for _ in 0..30 {
    let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1];
    
    // 各 med を取るようなクエリをリストアップしておく
    for i in 0..q {
        let med = (ng[i] + ok[i]) / 2;
        check[med].push(i);
    }

    let mut uf = UnionFind::new(n);

    // 順番に見ていき、 edge_id==med となるようなクエリについて ok と ng を更新する
    for edge_id in 0..m {
        uf.unite(a[edge_id], b[edge_id]);
        for query in check[edge_id].iter() {
            let from = uf.find(x[*query]);
            let to = uf.find(y[*query]);
            let count = if from == to {
                uf.sizes[from]
            } else {
                uf.sizes[from] + uf.sizes[to]
            };

            if count >= z[*query] {
                ok[*query] = edge_id;
            } else {
                ng[*query] = edge_id;
            }
        }
    }
}

問題

https://agc002.contest.atcoder.jp/tasks/agc002_d

コード

use std::io;

fn main() {
    let (n, m) = {
        let v = read_values::<usize>();
        (v[0], v[1])
    };
    let (a, b) = {
        let mut a = vec![0; m];
        let mut b = vec![0; m];
        for i in 0..m {
            let v = read_values::<usize>();
            a[i] = v[0] - 1;
            b[i] = v[1] - 1;
        }
        (a, b)
    };
    let q = read_values::<usize>()[0];
    let (x, y, z) = {
        let mut x = vec![0; q];
        let mut y = vec![0; q];
        let mut z = vec![0; q];
        for i in 0..q {
            let v = read_values::<usize>();
            x[i] = v[0] - 1;
            y[i] = v[1] - 1;
            z[i] = v[2];
        }
        (x, y, z)
    };
    

    let mut ng = vec![0; q];
    let mut ok = vec![m; q];

    for _ in 0..30 {
        let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1];
        for i in 0..q {
            let med = (ng[i] + ok[i]) / 2;
            check[med].push(i);
        }

        let mut uf = UnionFind::new(n);
        for edge_id in 0..m {
            uf.unite(a[edge_id], b[edge_id]);
            for query in check[edge_id].iter() {
                let from = uf.find(x[*query]);
                let to = uf.find(y[*query]);
                let count = if from == to {
                    uf.sizes[from]
                } else {
                    uf.sizes[from] + uf.sizes[to]
                };

                if count >= z[*query] {
                    ok[*query] = edge_id;
                } else {
                    ng[*query] = edge_id;
                }
            }
        }
    }

    for i in 0..q {
        println!("{}", ok[i] + 1);
    }
}

struct UnionFind {
    parent: Vec<usize>,
    sizes: Vec<usize>,
    size: usize,
}

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

    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]
        }
    }

    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;
        return true;
    }
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

ベイエリアでソフトウェアエンジニアとして働いてわかった、たった 1 つのこと

---------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------

1. ベイエリアにはガルパン上映館が 1 つもない。

CODE FESTIVAL 2017 Final E - Combination Lock

問題

E - Combination Lock

解法

方針としては、

1. 区間を整理しやすいように文字列の長さを偶数にする。
2. 区間の整理をめっちゃ頑張る
3. 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO

文字列の長さを偶数にする

文字列の長さが奇数だった場合、中央の文字に対する操作が何回行われても結果に影響はないので、中央の文字とそれに対する操作を削除して考えても変わりません。よって、入力を整理して、文字列の長さは必ず偶数であるとして考えます。

中央を覆う区間に対する操作

例えば、長さ 8 の文字列の [1, 5] 文字目に対する操作があった時、回分にするためには 4 文字目と 5 文字目を同じ文字にする必要がありますが、この操作によって 4 文字目と 5 文字目の差は変わらないため、この操作による 4 文字目と 5 文字目への影響は無視できます。よって、長さ 8 の文字列の [1, 5] 文字目に対する操作は [1, 3] 文字目に対する操作と考えることができます。

このように中央を越える区間に対する操作は、中央を挟んだ無視できる区間への影響を無視することで、より小さい区間への操作に置き換えることができます。これによって全ての操作を、中央から見て右側か左側のどちらかに収まるものとして考えることができます。

片側に寄せる

ある区間に対する操作を 26 回行うのと 0 回行うのは同じです。よってある区間に対する操作を 25 回行うのと -1 回行うのは同じことがわかります。中央から見て右側にある区間に対する操作は、中央から見て対称な左側の区間に対する操作に置き換えられます。例えば、長さ 8 の文字列について、 [6, 8] 文字目に対する操作を 1 回行うことは、 [1, 3] 文字目に対する操作を -1 回行うのと同じです。

このことから、全ての区間を左側に集め、左側に対して操作を行うことで右側の文字列を作って行く問題と考えることができます。

区間の整理

片方の端が同じ値である2つの区間に対する各操作は、区間が被らない操作として考えることが出来ます。例えば、区間 [a, b] に対する操作 1 と、区間 [a, b+k] に対する操作 2 があって操作 1 を m 回行って操作 2 を n 回行うのは、区間 [a, b] に対する操作を 2m 回行って、区間 [b+1, b+k] に対する操作を n 回行うのと同じです。

よって上の図のように 4 つの区間がある時、下の図のようにそれぞれが被らない区間の操作に置き換えることができます。

累積和

imos 法

コード

use std::io;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::collections::BTreeSet;

fn main() {
    let s = read_line().trim().to_owned();
    let n = s.len();
    let methods = read_values::<usize>()[0];
    let mut segments = Vec::new();
    for _ in 0..methods {
        let input = read_values::<usize>();
        let mut l: usize = input[0] - 1;
        let mut r: usize = input[1] - 1;
        let half = n >> 1;

        if (n & 1) == 1 {
            // 文字列の長さが奇数の時、中央の文字を削除するために区間を整理する
            if l == half && r == half {
                // 中央の 1 文字のみに対する操作は意味がないので無視する
                continue;
            }

            // 中央の文字を削除する分だけ 1 文字分ずらす
            if half < l {
                l -= 1;
            }
            if half <= r {
                r -= 1;
            }
        }
        segments.push((l, r));
    }

    // 長さが奇数の時、中央の文字を削除する
    let s = {
        let t = s.bytes().map(|c| {
            c - "a".bytes().next().unwrap()
        }).collect::<Vec<_>>();
        let mut polished = Vec::new();
        for i in 0..n {
            if (n & 1) != 1 || (n >> 1) != i {
                polished.push(t[i]);
            }
        }
        polished
    };

    // 新しい文字列の長さ
    let n = s.len();

    // 区間の左端をキーにして、左端の値の set を持つ
    let mut right_map: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new();
    for x in segments.iter() {
        let (l, r) = *x;

        let half = n >> 1;
        let (l, r) = if r < half {
            // 中央から見て左側の区間はそのまま使う
            (l, r)
        } else if l >= half {
            // 中央から見て右側の区間は左側に移す
            (n - 1 - r, n - 1 - l)
        } else {
            // 中央を越える区間を整理する
            let right_side = r - (half - 1);
            let left_side = half - l;

            if right_side > left_side {
                // 中央から見て右のほうが大きい区間
                let tmp_l = half + left_side;
                (n - 1 - r, n - 1 - tmp_l)
            } else if right_side == left_side {
                // 中央から見て対称な区間に対する操作は結果に影響がないので無視する
                continue;
            } else {
                // 中央から見て左のほうが大きい区間
                (l, half - 1 - right_side)
            }
        };

        if !right_map.contains_key(&l) {
            right_map.insert(l, BTreeSet::new());
        }
        right_map.get_mut(&l).unwrap().insert(r);
    }

    // 区間の右端をキーとした map も作る
    let mut left_map = BTreeMap::new();
    for (left, rights) in right_map.iter() {
        for r in rights.iter() {
            if !left_map.contains_key(&(r + 1)) {
                left_map.insert(r + 1, BTreeSet::new());
            }
            left_map.get_mut(&(r + 1)).unwrap().insert(*left);
        }
    }

    // 区間を整理する
    let mut merged_map = BTreeMap::new();
    for left in 0..n {
        // left を左端に持つ区間がなければスルー
        if !right_map.contains_key(&left) {
            continue;
        }

        let mut lefts = BTreeSet::new();

        let mut queue = VecDeque::new();
        queue.push_back(left);
        let mut right = left;
        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            lefts.insert(v);

            if let Some(set) = right_map.remove(&v) {
                for r in set.iter() {
                    queue.push_back(*r + 1);
                    right = cmp::max(right, *r + 1);
                }
            }

            if let Some(set) = left_map.remove(&v) {
                for l in set.iter() {
                    queue.push_back(*l);
                }
            }
        }
        lefts.insert(right);

        let list = lefts.iter().map(|x| x.clone()).collect::<Vec<_>>();
        for i in 0..(list.len() - 1) {
            let cur = list[i];
            let next = list[i + 1];
            merged_map.insert(cur, next);
        }
    }

    let mut sum = vec![0; n / 2 + 1];
    let mut cur = 0;
    for i in 0..(n / 2) {
        cur += sum[i];
        let from = (s[i] as i64 + cur) % 26;
        let to = (s[n - 1 - i] as i64) % 26;
        let add = (to + 26 - from) % 26;
        if add == 0 {
            continue;
        }
        if !merged_map.contains_key(&i) {
            println!("NO");
            return;
        }
        let x = *merged_map.get(&i).unwrap();
        cur += add;
        sum[x] -= add;
    }
    println!("YES");
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

AtCoder Problems を支える技術

adventar.org

はじめに

AtCoder Problems というサービスを作っています。最近作り直しています。

http://beta.kenkoooo.com/atcoder/

これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・

ソースコードも公開しています。このプログラムの中でどんなことをしているのかを書いていきたいと思います。競技プログラミングはそんなに関係ないです。

github.com

スクレイパー

Scala で書いています。ScalaScraper でクロールもスクレイピングもやってくれるので、それに任せています。

やっていることは以下のとおりです。

• コンテスト一覧をクロールして DB に入れる。
• DB のコンテストを順番に見ていき、そのコンテストの問題をクロールして DB に入れる。
• コンテストを順番に見ていき、そのコンテストの提出をクロールして DB に入れる。全てクロールすると多すぎるので、既に DB に入っている提出が出るまで最新の方から見てクロールする。
• クロール漏れするかもしれないので 1 日に 4 回だけ全ての提出をクロールする。

集計

ユーザーが問題を解いた数や、各問題の正解者数、実行速度最速の提出やコード長が最短の提出などを集計しています。これらの値は API でリクエストが来ますが、来るたびに計算していると遅いので予め計算しておきます。やっていることは SQL クエリを投げるだけです。ユーザーの提出をできるだけ早めに反映するため 5 分ごとくらいで実行しています。

API サーバー

フロントエンドからは JSON で出力を返す API を叩いています。API サーバーも Scala で書かれていて、サーバーは Akka HTTP で、SQL 部分は ScalikeJDBC を使って書いています。

可能ならレスポンスを gzip で返したり、ETag を見て変更がなければ 304 を返してキャッシュを使ってもらったりなどの工夫がありますが、このへんは Akka HTTP がよしなにやってくれています。

フロントエンド

フロントエンドは TypeScript と React で書いています。JS 業界は gulp だの bower だの browserify だの webpack だの mocha だの chai だの無限にインストールしなければならないイメージでしたが、TypeScript のチュートリアルどおりにやったところ、トランスパイルは webpack 、テストは jest だけで十分でした。

TypeScript は VSCode でプラグイン無しで快適に書けるのでとても良いです。素の JavaScript を書くことは一生ないでしょう。

得点の予測

AtCoder の rated のコンテストでは各問題に得点が設定されていますが、そうでない問題は rated の問題と違う基準で得点が設定されているので、推定してみることにしました。

AtCoder で 300 問以上解いているユーザーをヘビーユーザーとして、ヘビーユーザーの各問題についての「解けた」「提出したが不正解だった」「提出していない」を特徴量にして、思考停止 XGBoost で predict しました。

AtCoder で問題を解くと、ヘビーユーザーとして特徴量作成に使われたり、各問題の特徴が正確になったりして、反映される予測値も正確になっていくはずなので、みなさん問題を解きましょう。

まとめ

Scala はいい。TypeScript もまあいい。