エンジニアの kenkoooo です。最近は、我々の開発した機械学習による予測アルゴリズムがリリースされ、ログを見ながら一喜一憂する日々です。

さて、RCO プロコン部では、日々プログラミングコンテストに関する情報を共有したり、コンテストに参加したりしていますが、今回は Indeed やドワンゴといった競技プログラマの集まる会社を招待して、交流も兼ねたコンテストを開催しました。

コンテストの様子

RCO 社員も含めて 30 人以上が参加しました。所属は違っても、かつて ICPC で競い合ったライバルだったりするので、同窓会のような雰囲気です。

今回は問題セットとして Hello 2015 というコンテストの問題を使いました。また、 uwi さんがオープンソースの順位表にクローラーを組合せて、リアルタイムに順位が変動する順位表を作ってくれました。

ペアプロしているチームもありました。

結果

正答数	チーム	A	B	C	D	E	F
4	climpet, kenkoooo, hiro116s, suikabenzene, TangentDay	-	o	o	o	o	-
3	kawatea, kyuridenamida, shiratty8, kojingharang	x	o	-	o	o	-
3	tomerun, __math, nikeeshi, yaoshimax	o	o	-	-	o	-
2	Mi_Sawa, tayama, eha, ukikagi	-	o	-	o	-	-
2	sky58, roiti46, cympfh, yamamon	-	o	-	o	-	-
1	uwi, dpforest, blue_jam, eomole	-	x	-	-	o	-
1	rankalee, amylase, zukky, iehn, gahou	-	x	-	o	-	-
1	kcm1700, KenjiH, Footman, no15_renne	x	x	-	o	-	-

全体的に実装が重めだったのと、一番簡単な B 問題が罠が多い問題で、どのチームも苦しそうでした。私のチームでは序盤で B, C, D, E の解法が出揃っていたものの、どれも実装がややこしく、後半で climpet さんが D を、suikabenzene さんが B を通してやっと 2 完というところでした。しかし、終盤で hiro116s さんが E 問題を通し、さらに、新幹線の終電で先に離脱した TangentDay さんが、会場で通らなかったコードに枝刈りを入れて新幹線から通すという離れ業を見せて 1 位に浮上するなどのドラマがありました。

終わった後は、各問題の正解者に解説をしてもらいました。

C問題レビュー

コンテスト中は僕は 1 問も実装せずに TangentDay さんが考えた C 問題の解法を聞いていただけでしたが、せっかくなので C 問題を実装してみました。

解法

問題リンク

Q 個のクエリについて、全ての長方形を列挙すると O(N^2 M^2 Q) の時間がかかり、さらに長方形内の最小値と最大値をとっていたりすると、とても間に合いません。そこで、全ての長方形を列挙するのをやめて、一方の辺のみ列挙することにします。一方の辺を固定できれば、他方の辺は しゃくとり法 と呼ばれる方法によって、全パターンを網羅することができそうです。しゃくとり法をしながら区間に含まれる最小値や最大値を O(1) で求める手法として、 スライド最小値 と呼ばれる方法があります。

一方の辺を全列挙するのに O(M^2) 、しゃくとり法で他方の辺を網羅するのに O(N) これを Q 個のクエリについて行うので、全体で O(N M^2 Q) の計算時間で答えを求めることができます。

実装例

use std::io;
use std::str;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;

macro_rules! back {
    ($e:expr) => (*$e.back().unwrap());
}
macro_rules! front {
    ($e:expr) => (*$e.front().unwrap());
}

fn main() {
    let nmq = readv::<usize>();
    let (n, m, q) = (nmq[0], nmq[1], nmq[2]);

    let map = (0..n).map(|_| readv::<i32>()).collect::<Vec<_>>();
    let queries = (0..q).map(|_| read::<i32>()).collect::<Vec<_>>();

    let mut min_deq: VecDeque<usize> = VecDeque::new();
    let mut max_deq: VecDeque<usize> = VecDeque::new();

    let mut ans = vec![0;q];

    let mut min = vec![0;n];
    let mut max = vec![0;n];

    for l in 0..m {
        for r in l + 1..m + 1 {
            for i in 0..n {
                if r - l == 1 {
                    min[i] = map[i][l];
                    max[i] = map[i][l];
                } else {
                    min[i] = cmp::min(map[i][r - 1], min[i]);
                    max[i] = cmp::max(map[i][r - 1], max[i]);
                }
            }

            for p in 0..q {
                let k = queries[p];

                let mut head_idx = 0;
                min_deq.clear();
                max_deq.clear();

                for bottom_idx in 0..n {
                    while !min_deq.is_empty() && min[back!(min_deq)] >= min[bottom_idx] {
                        min_deq.pop_back();
                    }
                    while !max_deq.is_empty() && max[back!(max_deq)] <= max[bottom_idx] {
                        max_deq.pop_back();
                    }
                    
                    max_deq.push_back(bottom_idx);
                    min_deq.push_back(bottom_idx);

                    while head_idx <= bottom_idx &&
                          max[front!(max_deq)] - min[front!(min_deq)] > k {
                        head_idx += 1;
                        if front!(min_deq) < head_idx {
                            min_deq.pop_front();
                        }
                        if front!(max_deq) < head_idx {
                            max_deq.pop_front();
                        }
                    }
                    ans[p] += (bottom_idx as i64) - (head_idx as i64) + 1;
                }
            }
        }
    }

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

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}
#[allow(dead_code)]
fn read<T>() -> T
    where T: std::str::FromStr,
          T::Err: std::fmt::Debug
{
    read_line().trim().parse().unwrap()
}
#[allow(dead_code)]
fn readv<T>() -> Vec<T>
    where T: std::str::FromStr,
          T::Err: std::fmt::Debug
{
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

（今年度アドテク部に入ってきた新卒の方が Rust 愛の強い方で、僕も影響されて Rust を勉強し始めました。まだ Rust らしいコードにはほど遠いですが……）

寿司

人数の多い勉強会では寿司のグレードが上がることがあります。

広告

RCO アドテク部では、プログラミングコンテスト、あるいは寿司、もしくは Rust が好きなエンジニアも募集しています。

採用ページ