AGC036 B - Do Not Duplicate

問題

atcoder.jp

解法

s の先頭の数字と同じ数字が来たら s が空になることを考える。例えば a(0)=a(i), a(i+1)=a(j) のとき、s は i で空になり、jで再び空になる。鳩の巣原理より a0 が何周目で再び先頭になるかO(N)で求めることができる。

a0 が先頭になった場合、再び a0 が先頭になるまでに要するステップは変わらないので、最後のN*K%周期くらいを愚直にやれば良い。

コード

use std::collections::BTreeSet;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let k: usize = sc.read();
    let a: Vec<usize> = sc.vec(n);
    let max_a = a.iter().cloned().max().unwrap();
    let mut next = vec![vec![]; max_a + 1];
    let mut pos = vec![0; n];
    for (i, &a) in a.iter().enumerate() {
        pos[i] = next[a].len();
        next[a].push(i);
    }

    let mut jumped = false;
    let mut cur_t = 0;
    let mut cur_pos = 0;
    let mut prev = vec![std::usize::MAX; n];
    prev[0] = cur_t;
    loop {
        let pos = pos[cur_pos];
        if next[a[cur_pos]].len() == pos + 1 {
            if cur_t == k - 1 {
                let mut ans = vec![];
                let mut set = BTreeSet::new();
                for i in cur_pos..n {
                    if set.contains(&a[i]) {
                        while let Some(tail) = ans.pop() {
                            set.remove(&tail);
                            if tail == a[i] {
                                break;
                            }
                        }
                    } else {
                        ans.push(a[i]);
                        set.insert(a[i]);
                    }
                }

                for (i, a) in ans.into_iter().enumerate() {
                    if i > 0 {
                        print!(" ");
                    }
                    print!("{}", a);
                }
                println!();
                return;
            }
            cur_t += 1;
            cur_pos = next[a[cur_pos]][0];
        } else {
            cur_pos = next[a[cur_pos]][pos + 1]
        }
        cur_pos += 1;
        if cur_pos == n {
            if cur_t == k - 1 {
                println!();
                return;
            }
            cur_t += 1;
            cur_pos = 0;
        }
        if !jumped && prev[cur_pos] < cur_t {
            let dt = cur_t - prev[cur_pos];
            let z = (k - prev[cur_pos] - 1) / dt;
            cur_t = prev[cur_pos] + dt * z;
            assert!(cur_t < k);
            jumped = true;
        } else {
            prev[cur_pos] = cur_t;
        }
    }
}

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')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}

ABC139 F - Engines

問題

atcoder.jp

解法

答えとなるベクトル v があったとして、それを作るには v となす角が 90° 未満のベクトル集合のみを考えれば良い。よって、最終的に使われるベクトル集合は偏角ソートしたときに連続した区間になっているはずである。Nが小さいので全ての連続区間について愚直に計算する。

コード

use std::cmp::max;
use std::collections::BTreeMap;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut xy = vec![];
    for _ in 0..n {
        let x: i64 = sc.read();
        let y: i64 = sc.read();
        xy.push((x, y));
    }

    xy.sort_by(|&(x1, y1), &(x2, y2)| {
        let t1 = (y1 as f64).atan2(x1 as f64);
        let t2 = (y2 as f64).atan2(x2 as f64);
        t1.partial_cmp(&t2).unwrap()
    });

    let tmp = xy.clone();
    xy.extend(tmp);

    let mut ans = 0;
    for head in 0..n {
        for tail in head..(head + n) {
            let mut cur = (0, 0);
            for i in head..(tail + 1) {
                cur.0 += xy[i].0;
                cur.1 += xy[i].1;
            }
            let (x, y) = cur;
            ans = max(ans, x * x + y * y);
        }
    }
    println!("{}", (ans as f64).sqrt());
}

fn update_max<T: PartialOrd>(a: &mut T, b: T) {
    if *a < b {
        *a = b;
    }
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b.abs(), a.abs() % b.abs())
    }
}

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')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}

ABC139 E - League

問題

atcoder.jp

解法

順番を並び替えることを考える余地はなく、「今日試合ができる組は全員試合をする」を毎日繰り返す。

コード

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

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

    let n: usize = sc.read();
    let a: Vec<Vec<_>> = (0..n)
        .map(|_| (1..n).map(|_| sc.read::<usize>() - 1).collect())
        .collect();
    let mut pos = vec![0; n];
    let mut q = VecDeque::new();
    for i in 0..n {
        let j = a[i][0];
        if a[j][0] == i && i < j {
            q.push_back((i, j, 1));
        }
    }

    let mut t = 0;

    while let Some((i, j, time)) = q.pop_front() {
        t = max(t, time);
        pos[i] += 1;
        if pos[i] < n - 1 {
            let j = a[i][pos[i]];
            if a[j][pos[j]] == i {
                q.push_back((i, j, time + 1));
            }
        }

        let i = j;
        pos[i] += 1;
        if pos[i] < n - 1 {
            let j = a[i][pos[i]];
            if a[j][pos[j]] == i {
                q.push_back((i, j, time + 1));
            }
        }
    }

    if pos.into_iter().all(|x| x == n - 1) {
        println!("{}", t);
    } else {
        println!("-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')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}

飲酒プログラミングコンテストに参加した

注意(2019/09/01 追記)

この記事は過度な飲酒を推奨するものではありません。飲酒プログラミングコンテストでは速く飲むことを重視するあまり、過度に飲酒を行ってしまう傾向があります。開催する場合、その危険性を十分認識した上で自己責任で行ってください。また、最悪の事態に備えてシラフで判断力のある人間を用意することを強く推奨します。

原作

wass80.hateblo.jp

amylase さんがこの記事に感銘を受けて飲酒プログラミングコンテストを開いたので参加した。

コンテストの様子

amylase さん謹製の統計モデルで、難易度が易しいものから難しいものまで揃うように問題セットが組まれた。

参加者の酒の好みが分かれたので、ルールはアルコール体積ベースになった。唯一の青コーダーなので、銀〜黄の皆様が酒で破滅することを願いながらハイボールを開けた。

実際にやってみるとまず1缶目が空かない。レート差を埋めるためにはサクサク飲んでいかねばならないので焦る。tokoharu 先生は 45ml のウイスキーをストレートで飲み干して問題を解き始めている。橙コーダーが酒に強いと勝ち目がないのでやめろ。

1 問目 Garbage Collector

atcoder.jp

ようやく1缶目のハイボールが空いたので問題を開く。問題を開くコストが重いので最終問から開くのは悪手に思えるが、知っている問題だったので酩酊実装力を信じて勝負に出た。

ロボットをk台として累積和を回してやれば調和級数の和で O(N log N) で解けるという方針が立つ(知っているので)。Rust で実装し始めるが手元がおぼつかない。実装も終わったのにコンパイルが通らない。全部ミュータブルでええやろ!wコンパイルは通るようになったが、今度は配列外参照でサンプルが通らない。サンプルが間違っている。

順位表を見ると早くも not さんと yosupo さんが WA を出している。始まってきたな。

手元のコードは相変わらずサンプルが通らない。ランタイムエラーは消えたが数字が合わない。やはりサンプルが間違っている。コードを読む能力は失われているため print デバッグすると n と m を取り違えていた。競技プログラマは1文字変数を使うのでダメ。

サンプルが合ったので提出する。

atcoder.jp

一 発 A C

1000 以上あるレート差をひっくり返している。適性があるかもしれない。問題を読む権利が無いので2本目のハイボールを手に取る。

缶で飲むよりも一旦グラスに移して飲む方が流体力学的に早く飲めるという知見が得られた。破滅しそう。

2 問目 Megalomania

atcoder.jp

2 問目は無難に一番最初の問題を開いた。おそらく解いたことがない。

区間スケジューリングっぽい。蟻本で見た。早く終わらせないといけない仕事から順番にやっていけばええやろ!w俺は蟻本を3冊持ってる男やぞ。

atcoder.jp

一 発 A C

敗北を知りたい。

初手ウイスキーストレートをキメていた tokoharu 先生が print デバッグで苦しんでいる様子だったのでとりあえず煽っとく。

3 本目のハイボールは最初からグラスに移して飲み干した。やはり缶で飲むよりも流量が大きいので速く飲むのに適している。

3 問目 Successive Subtraction

atcoder.jp

3 問目も何も考えずに前から開く。

普通に難しくない?

解けないことが分かってしまった。

とりあえず一番小さいやつをメチャクチャ小さくして大きいやつから引けば良さそう。サンプルが合うので提出する。流石に 3 完すれば優勝間違いないでしょ。

atcoder.jp

WA

tokoharu 先生がいつの間にか追い上げてきている。ウイスキーの小瓶も空になっている。どうなってんの。

4 本目のハイボールが空かない。アルコールもそうだが普通に体積が厳しい。残り時間も少ないので飲み切らなくてもギリギリペナルティ差で逃げ切れそう。

結果

こんな破滅的なコンテストで発揮される勝負強さ、何なの?

ABC137 D - Summer Vacation

問題

atcoder.jp

解法

どの仕事も1日で終わるので、もらえる金額が大きければ大きいほどよい。よってもらえる金額が大きい方から処理していく。もらえる金額が同じ仕事同士では、振込が早い仕事よりも遅い仕事の方が候補日が限られるので、遅い仕事から処理する。

ある仕事 i を引き受けるかどうかを決めるとき、M-a_i日目までに終わらせなければならない。1日目〜M-a_i日目の間でまだ仕事を入れていない日があれば、そこに仕事を入れる。もし埋まっていた場合、そこを埋めている仕事は必ず仕事i以上の給料の仕事なので、仕事iと入れ替えても総額は上がらない。よって仕事iを引き受けなくて良いことになる。

これらを繰り返していくことで最適解が得られる。

コード

use std::collections::BTreeSet;

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

    let mut tasks = vec![];
    for _ in 0..n {
        let days: usize = sc.read();
        let value: u64 = sc.read();
        tasks.push((value, days));
    }
    tasks.sort();
    tasks.reverse();
    let mut remain = (0..(m + 1)).collect::<BTreeSet<_>>();
    let mut ans = 0;
    for (value, days) in tasks.into_iter() {
        if m < days {
            continue;
        }
        let d = m - days;
        if let Some(&d) = remain.range(..(d + 1)).next_back() {
            remain.remove(&d);
            ans += value;
        }
    }
    println!("{}", ans);
}

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')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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 Beginner Contest 136 F - Enclosed Points

問題

atcoder.jp

解法

各点について、自分の (左上、右上、左下、右下) にある点の数を数える。これは 座標圧縮 => Fenwick Tree で O(N logN) でできる。

各点について、その点を含まない長方形の数は以下の合計である。

  • 右下の空でない点集合の数 * 右上の空でない点集合の数
  • 右上の空でない点集合の数 * 左上の空でない点集合の数
  • 左上の空でない点集合の数 * 左下の空でない点集合の数
  • 左上の空でない点集合の数 * 右下の空でない点集合の数
  • 右下の空でない点集合の数
  • 右上の空でない点集合の数
  • 左上の空でない点集合の数
  • 左上の空でない点集合の数

この値の合計を、全ての空でない点集合に全ての点が含まれるとした値 N*(2^N-1) から引けば良い。

コード

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

const MOD: usize = 998244353;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut x = vec![];
    let mut y = vec![];
    for _ in 0..n {
        x.push(sc.read::<i64>());
        y.push(sc.read::<i64>());
    }

    let ans = solve(&x, &y);
    println!("{}", ans.0);
}

fn solve(x: &Vec<i64>, y: &Vec<i64>) -> ModInt<usize> {
    let n = x.len();
    let x = shrink(x);
    let y = shrink(y);
    let mut xy = vec![];
    for i in 0..n {
        xy.push((x[i], y[i]));
    }
    xy.sort();

    let mut upper_left = vec![0; n];
    let mut upper_right = vec![0; n];
    let mut lower_left = vec![0; n];
    let mut lower_right = vec![0; n];

    let mut left_bit = fenwick_tree::FenwickTree::new(n, 0);
    for x in 0..n {
        let (_, y) = xy[x];
        let upper = left_bit.sum(y, n);
        let lower = left_bit.sum(0, y);
        upper_left[x] = upper;
        lower_left[x] = lower;
        left_bit.add(y, 1);
    }
    let mut right_bit = fenwick_tree::FenwickTree::new(n, 0);
    for x in (0..n).rev() {
        let (_, y) = xy[x];
        let upper = right_bit.sum(y, n);
        let lower = right_bit.sum(0, y);
        upper_right[x] = upper;
        lower_right[x] = lower;
        right_bit.add(y, 1);
    }

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

    let mut ans = ModInt(0);
    for i in 0..n {
        let cycle = [
            upper_left[i],
            upper_right[i],
            lower_right[i],
            lower_left[i],
            upper_left[i],
        ];
        for i in 0..4 {
            let a = cycle[i];
            let b = cycle[i + 1];
            ans += (pow2[a] - 1) * (pow2[b] - 1);
            ans += pow2[a] - 1;
        }
    }
    (pow2[n] - 1) * n - ans
}

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, rhs: Num) -> ModInt<Num> {
            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, rhs: Num) -> ModInt<Num> {
            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, rhs: Num) -> ModInt<Num> {
            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 mod fenwick_tree {
    use std::ops::{AddAssign, Sub};
    /// `FenwickTree` is a data structure that can efficiently update elements
    /// and calculate prefix sums in a table of numbers.
    /// [https://en.wikipedia.org/wiki/Fenwick_tree](https://en.wikipedia.org/wiki/Fenwick_tree)
    pub struct FenwickTree<T> {
        n: usize,
        data: Vec<T>,
        init: T,
    }

    impl<T: Copy + AddAssign + Sub<Output = T>> FenwickTree<T> {
        /// Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`.
        pub fn new(size: usize, init: T) -> FenwickTree<T> {
            FenwickTree {
                n: size + 1,
                data: vec![init; size + 1],
                init: init,
            }
        }

        pub fn add(&mut self, k: usize, value: T) {
            let mut x = k;
            while x < self.n {
                self.data[x] += value;
                x |= x + 1;
            }
        }

        /// Returns a sum of range `[l, r)`
        pub fn sum(&self, l: usize, r: usize) -> T {
            self.sum_one(r) - self.sum_one(l)
        }

        /// Returns a sum of range `[0, k)`
        pub fn sum_one(&self, k: usize) -> T {
            assert!(k < self.n, "k={} n={}", k, self.n);

            let mut result = self.init;
            let mut x = k as i32 - 1;
            while x >= 0 {
                result += self.data[x as usize];
                x = (x & (x + 1)) - 1;
            }

            result
        }
    }
}
fn shrink(x: &Vec<i64>) -> Vec<usize> {
    let map = x
        .iter()
        .cloned()
        .collect::<BTreeSet<_>>()
        .into_iter()
        .enumerate()
        .map(|(i, e)| (e, i))
        .collect::<BTreeMap<_, _>>();
    x.iter().cloned().map(|x| *map.get(&x).unwrap()).collect()
}

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')
            .take_while(|&b| b != b' ' && b != b'\n')
            .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()
    }
}

HUPC 2019 日記

1日目

https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2019Day1/problems

Cinnamorollさんとasako9494さんと同じチームで出た。

Cの構文解析は誰もやりたがらないので放置された。DはO(1)でできそう感を感じつつ制約がO(N)を許容しているのでO(N)で通した。素直。

その間にCinnamorollさんがE問題を解き終わっていた。初期の解法では最短経路が複数あるケースを処理できなかったが、それを反例として挙げたらダイクストラっぽいシンプルな解法が発生してACされていた。すごい。問題自体もインタラクティブの面白さが感じられる良い問題だったと思った。

FはCinnamorollさんによって、状態+bitDPという示唆が与えられたが、僕がそこから嘘解法に走ってしまって無の時間を過ごした。途中でCinnamorollさんが僕の解法で処理できない遷移を図示してくれたが僕の理解力が低かったため特に何も起こらなかった。後で解いてみたら、かなり苦労したがシンプルなDPで解ける面白い問題だった(自分が解ける問題は面白い問題)

Gは想定TLE解法のO(NW^2)解法が生えたが、そこからどうしようもなくて終わった。

フィックスターズのスポンサーセッションがあった。競プロ勢の力を使って金儲けをしている会社が学生の競プロ活動に金を出すのは本当に良いことだと思う。(競プロをやっている学生を採用して実装力に乗っかっているのにコミュニティに還元しないタダ乗り企業はたくさんある)

懇親会でビールをたくさん飲んで鍋をこぼすなどした。懇親会を途中抜けしてAGCに出て他の参加者にレートを配るなどの慈善活動をして寝た。

2日目

https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2019Day2/problems

prd_xxxさんとnenaさんと同じチームで出た。ゴリラチームだったので知能を捨てた。

A問題とB問題をnenaさんがサブミットデバッグで通していた。ゴリラである。

C問題をprd_xxxさんが無証明エスパーで通していた。ゴリラである。

D問題をO(N^2)をbitsetで高速化してゴリ押しで通した。ゴリラである。

E問題はパンを得る最短経路問題とジャムを得る最短経路問題は独立の問題だということに気づき、それぞれを別に解いて最後に解を合わせた。ゴリラではない。一見してメチャクチャ難しそうに見えるのに愚直なダイクストラで解けるのは面白い。

F問題は愚直にやっても実は調和級数の和のアレでO(NlogN)しか区間が存在しないというのをそのまま実装して通した。ゴリラではない。

GもHも解けなそうだったので、ゴリラについて考えながら残りの時間を過ごした。

コンテスト後は、せっかく札幌に来たので、ガルパンを観たりDay1 Fを解いたりして過ごした。

そのほか

運営の方は本当にお疲れ様でした。参加できて良かったです。