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を解いたりして過ごした。

そのほか

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

HUPC 2019 Day1 F: グリッドの番号 (Grid Number)

解法

1から2nまでの数を順番にグリッドに詰めていく。このとき、各状態からの遷移は上段に詰めるか下段に詰めるかの2通りの遷移がある。

各状態を、「下段より右側に出ている上段の数の列に、今まで詰めた数の何個前の数字が入っているか」のビット列として表す。
例えば下の例では、4まで詰めて、上段で下段よりも飛び出している部分は2 4 5、すなわち3個前の数と1個前の数と0個前の数が入っているので、状態は1011と表せる。

1 2 4 5
3 

dp[i][state] をiまで詰めて、stateになっている時の組み合わせの数、として持っておけばシンプルな動的計画法で解ける。

コード

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 modulo: usize = sc.read();

    let mut dp = vec![vec![0; 1 << k]; 2 * n + 1];
    dp[0][0] = 1;
    for i in 0..(2 * n) {
        for mask in 0..(1 << k) {
            if mask == (1 << k) - 1 {
                continue;
            }
            if mask & (1 << (k - 1)) == 0 {
                let next = (mask << 1) | 1;
                dp[i + 1][next] += dp[i][mask];
                dp[i + 1][next] %= modulo;
            }
            if mask > 0 {
                let next = (mask - mask.highest_one_bit()) << 1;
                dp[i + 1][next] += dp[i][mask];
                dp[i + 1][next] %= modulo;
            }
        }
    }

    let mut ans = dp[2 * n][0];
    if n == k {
        ans += 1;
    }
    println!("{}", ans % modulo);
}

trait HighestOneBit {
    fn highest_one_bit(self) -> usize;
}

impl HighestOneBit for usize {
    fn highest_one_bit(self) -> usize {
        (self + 1).next_power_of_two() >> 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()
    }
}

ICFP Contest 2019 振り返りメモ

osak.hatenablog.jp

シミュレーターを作ってました。が、そこそこバグらせて結構迷惑をかけてしまいました……

雑感

  • 入出力を処理する実装がAI側とシミュレーター側にそれぞれ存在していて、片方で直したバグがもう片方(主に僕の方ですが…)で直っていなかったりして良くなかった。
    • ICFPC の入出力はたいてい面倒なので、競プロ形式みたいな共通のフォーマットを決めてやったほうが良さそうとは思いつつも、途中の仕様追加で全てが崩壊したりしそうで難しい。
  • Docker と Jenkins でデプロイがある程度自動化されていて快適だった。osa_kさんすごい。
    • しっかりDockerを使えばTypeScriptに縛られずかなり色んなことができたはずなので、もっとちゃんと乗っかればよかった。
  • ブラウザで動かすシミュレータ→React + TypeScript と短絡的に考えてしまったのはあまり良くなかった。
    • 全部をTypeScriptで実装する必要はなく、例えば塗り判定やアイテム取得のタイミングなどのややこしめの部分は Rust なり C++ なりで実装しておいて Wasm にしておくとかでも良かった。
    • 特に今回は mkut さんが便利ライブラリをC++で作っていたのでそれに乗っかったほうが良かった。
    • (そもそも初手のシミュレーターの設計が良くなかったΩ\ζ°)チーン)
  • なんとなく全体的に遠慮がちになってしまって、互いのコードの内容を把握していなくて良くなかった。
    • 寝る前に引き継ぎ的なのとかを軽くするだけでもだいぶ良くなりそう。

今日復習した問題

B - Splatter Painting

クエリを逆順にやればいいというのは「Pruned Landmark Labeling で見た!」という気持ちでやった。

use std::collections::VecDeque;

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

    let q: usize = sc.read();
    let queries = (0..q)
        .map(|_| (sc.read::<usize>() - 1, sc.read::<usize>(), sc.read::<u32>()))
        .collect::<Vec<_>>();
    let mut color = vec![0; n];

    let mut dist = vec![0; n];
    for (v, d, c) in queries.into_iter().rev() {
        let mut q = VecDeque::new();
        if color[v] == 0 {
            color[v] = c;
        }
        q.push_back((v, d));
        while let Some((v, d)) = q.pop_front() {
            if d == 0 {
                continue;
            }
            for &next in graph[v].iter() {
                if color[next] == 0 {
                    color[next] = c;
                }
                if dist[next] < d - 1 {
                    dist[next] = d - 1;
                    q.push_back((next, dist[next]));
                }
            }
        }
    }

    for color in color.into_iter() {
        println!("{}", color);
    }
}

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

C - Tree Restoring

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut a: Vec<usize> = sc.vec(n);
    a.sort();
    let max = a[n - 1];
    let mut count: Vec<u32> = vec![0; max + 1];
    for a in a.into_iter() {
        count[a] += 1;
    }

    for d in 0..(max + 1) {
        if d * 2 < max {
            if count[d] > 0 {
                println!("Impossible");
                return;
            }
        } else if d * 2 - 1 == max {
            if count[d] != 2 {
                println!("Impossible");
                return;
            }
        } else if d * 2 == max {
            if count[d] != 1 {
                println!("Impossible");
                return;
            }
        } else {
            if count[d] < 2 {
                println!("Impossible");
                return;
            }
        }
    }
    println!("Possible");
}

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

B - Colorful Hats

一見すると複雑そうだが、見える色の種類は実は高々2種類しか無いというのが面白い。

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

    let n: usize = sc.read();
    let a: Vec<usize> = sc.vec(n);
    let max: usize = a.iter().cloned().max().unwrap();
    let mut count = vec![0; max + 1];
    for a in a.into_iter() {
        count[a] += 1;
    }

    let candidates = count
        .iter()
        .enumerate()
        .filter(|&(_, &count)| count > 0)
        .map(|(i, _)| i)
        .collect::<Vec<_>>();
    if candidates.len() > 2 {
        println!("No");
        return;
    }

    if candidates.len() == 1 {
        let count = candidates[0];
        if count <= n / 2 || count == n - 1 {
            println!("Yes");
        } else {
            println!("No");
        }
        return;
    }
    let (c1, c2) = (candidates[0], candidates[1]);
    if count[c2] <= 1 || c1 + 1 != c2 {
        println!("No");
        return;
    }

    let different = count[c1];
    let same = count[c2];
    if c2 < different + 1 || different + same / 2 < c2 {
        println!("No");
        return;
    }

    println!("Yes");
}

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

C - Ants on a Circle

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

    let n: usize = sc.read();
    let l: u64 = sc.read();
    let t: u64 = sc.read();
    let xw: Vec<_> = (0..n)
        .map(|_| (sc.read::<u64>(), sc.read::<u32>() == 1))
        .collect();

    let n = n as u64;
    let mut clock_count = 0;
    let mut counter_count = 0;
    for &(x, clockwise) in xw.iter() {
        if clockwise {
            clock_count += (x + t) / l;
        } else {
            counter_count += (l - x + t - 1) / l;
        }
    }

    clock_count %= n;
    counter_count %= n;
    let mut end_state = xw
        .iter()
        .map(|&(x, clockwise)| {
            if clockwise {
                ((x + t) % l, clockwise)
            } else {
                ((l - (l - x + t) % l) % l, clockwise)
            }
        })
        .collect::<Vec<_>>();
    end_state.sort();
    let first = (clock_count - counter_count + n) % n;
    for i in 0..n {
        println!("{}", end_state[((first + i) % n) as usize].0);
    }
}

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

C - Closed Rooms

2周目以降はただのBFSになるということに気づくと実装がすごくシンプルになって気持ちいい。

use std::collections::VecDeque;

const INF: u64 = 1e15 as u64;

const DX: [i64; 4] = [0, 0, 1, -1];
const DY: [i64; 4] = [1, -1, 0, 0];

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let k: u64 = sc.read();
    let s: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut dist = vec![vec![INF; w]; h];
    let mut q = VecDeque::new();
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 'S' {
                dist[i][j] = 0;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("1");
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 && s[ni][nj] != '#' && dist[i][j] + 1 <= k {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            if dist[i][j] != INF {
                dist[i][j] = k;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("{}", (dist[i][j] + k - 1) / k);
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }
}

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

E - Prefix-free Game

実験のコードを盛大にバグらせてひどい目にあった。

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

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let l: usize = sc.read();
    let mut trie = Trie::default();
    for _ in 0..n {
        let s = sc.chars();
        trie.add(s, 0);
    }

    let mut result = vec![];
    trie.traverse(l, &mut result);
    let result = result
        .into_iter()
        .map(|r| 1 << r.trailing_zeros())
        .fold(0, |xor, r| xor ^ r);
    println!("{}", if result != 0 { "Alice" } else { "Bob" });
}

struct Trie {
    zero: Option<Box<Trie>>,
    one: Option<Box<Trie>>,
}

impl Default for Trie {
    fn default() -> Trie {
        Trie {
            zero: None,
            one: None,
        }
    }
}
impl Trie {
    fn traverse(&self, l: usize, result: &mut Vec<usize>) {
        if self.zero.is_none() != self.one.is_none() {
            result.push(l);
        }
        if let Some(one) = self.one.as_ref() {
            one.traverse(l - 1, result);
        }
        if let Some(zero) = self.zero.as_ref() {
            zero.traverse(l - 1, result);
        }
    }

    fn add(&mut self, s: Vec<char>, pos: usize) {
        if s.len() == pos {
            return;
        }
        match s[pos] {
            '0' => {
                if self.zero.is_none() {
                    self.zero = Some(Box::new(Trie::default()));
                }
                self.zero.as_mut().unwrap().add(s, pos + 1);
            }
            '1' => {
                if self.one.is_none() {
                    self.one = Some(Box::new(Trie::default()));
                }
                self.one.as_mut().unwrap().add(s, pos + 1);
            }
            _ => unreachable!(),
        }
    }
}

fn grundy(h: usize, map: &mut BTreeMap<usize, usize>) -> usize {
    if map.contains_key(&h) {
        return *map.get(&h).unwrap();
    }
    let mut set = BTreeSet::new();
    for add in 1..(h + 1) {
        let mut g = 0;
        for r in 1..add {
            g ^= grundy(h - r, map);
        }
        set.insert(g);
    }

    let g = (0..).find(|x| !set.contains(x)).unwrap();
    map.insert(h, g);
    g
}

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

E - Or Plus Max

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let a: Vec<u64> = sc.vec(1 << n);
    let mut top2 = vec![vec![]; 1 << n];
    for mask in 0..(1 << n) {
        top2[mask].push((a[mask], mask));
    }
    for mask in 0..(1 << n) {
        for i in 0..n {
            let next_mask = mask | (1 << i);
            let top2_mask = top2[mask].clone();
            top2[next_mask].extend(top2_mask);
            top2[next_mask].sort();
            top2[next_mask].dedup();
            top2[next_mask].reverse();
            if top2[next_mask].len() > 2 {
                top2[next_mask].resize(2, (0, 0));
            }
        }
    }

    let mut max = 0;
    for mask in 1..(1 << n) {
        let (a, _) = top2[mask][0];
        let (b, _) = top2[mask][1];
        max = cmp::max(max, a + b);
        println!("{}", max);
    }
}

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

C - Nuske vs Phantom Thnook

森において、頂点の数-辺の数=木の数 になるの面白い。

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 q: usize = sc.read();
    let s: Vec<Vec<_>> = (0..n)
        .map(|_| {
            sc.chars()
                .into_iter()
                .map(|c| c as u32 - '0' as u32)
                .collect()
        })
        .collect();

    let sum = CumulativeSum::new(&s, 0);
    let h_sum = match n {
        1 => None,
        _ => {
            let mut h_edges: Vec<Vec<u32>> = vec![vec![0; m]; n - 1];
            for i in 1..n {
                for j in 0..m {
                    h_edges[i - 1][j] = if s[i][j] == 1 && s[i - 1][j] == 1 {
                        1
                    } else {
                        0
                    };
                }
            }
            Some(CumulativeSum::new(&h_edges, 0))
        }
    };

    let v_sum = match m {
        1 => None,
        _ => {
            let mut v_edges: Vec<Vec<u32>> = vec![vec![0; m - 1]; n];
            for i in 0..n {
                for j in 1..m {
                    v_edges[i][j - 1] = if s[i][j - 1] == 1 && s[i][j] == 1 {
                        1
                    } else {
                        0
                    };
                }
            }
            Some(CumulativeSum::new(&v_edges, 0))
        }
    };

    for _ in 0..q {
        let x1 = sc.read::<usize>() - 1;
        let y1 = sc.read::<usize>() - 1;
        let x2 = sc.read::<usize>() - 1;
        let y2 = sc.read::<usize>() - 1;

        let mut v = sum.get_sum(x1, y1, x2, y2);
        match v_sum {
            Some(ref v_sum) if y1 < y2 => {
                v -= v_sum.get_sum(x1, y1, x2, y2 - 1);
            }
            _ => {}
        }
        match h_sum {
            Some(ref h_sum) if x1 < x2 => {
                v -= h_sum.get_sum(x1, y1, x2 - 1, y2);
            }
            _ => {}
        }
        println!("{}", v);
    }
}
pub struct CumulativeSum<T> {
    ny: usize,
    nx: usize,
    sum: Vec<Vec<T>>,
}

impl<T> CumulativeSum<T>
where
    T: Copy + std::ops::Add<Output = T> + std::ops::Sub<Output = T>,
{
    pub fn new(a: &Vec<Vec<T>>, init: T) -> CumulativeSum<T> {
        assert!(a.len() > 0);
        let ny = a.len();
        let nx = a[0].len();
        let mut sum = vec![vec![init; nx + 1]; ny + 1];
        for i in 0..ny {
            for j in 0..nx {
                sum[i + 1][j + 1] = a[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
            }
        }
        CumulativeSum {
            ny: ny,
            nx: nx,
            sum: sum,
        }
    }

    pub fn get_sum(&self, y1: usize, x1: usize, y2: usize, x2: usize) -> T {
        assert!(y1 <= y2 && x1 <= x2);
        assert!(y2 <= self.ny - 1);
        assert!(x2 <= self.nx - 1);
        return self.sum[y2 + 1][x2 + 1] + self.sum[y1][x1]
            - self.sum[y1][x2 + 1]
            - self.sum[y2 + 1][x1];
    }
}
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()
    }
}

C - +/- Rectangle

また解けなかった。「H x W の問題を解くために、より難しい 1 x W の問題を解く」という発想が出てこなかった。

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

    let n: usize = sc.read();
    let a: Vec<usize> = sc.vec(n);
    let max: usize = a.iter().cloned().max().unwrap();
    let mut count = vec![0; max + 1];
    for a in a.into_iter() {
        count[a] += 1;
    }

    let candidates = count
        .iter()
        .enumerate()
        .filter(|&(_, &count)| count > 0)
        .map(|(i, _)| i)
        .collect::<Vec<_>>();
    if candidates.len() > 2 {
        println!("No");
        return;
    }

    if candidates.len() == 1 {
        let count = candidates[0];
        if count <= n / 2 || count == n - 1 {
            println!("Yes");
        } else {
            println!("No");
        }
        return;
    }
    let (c1, c2) = (candidates[0], candidates[1]);
    if count[c2] <= 1 || c1 + 1 != c2 {
        println!("No");
        return;
    }

    let different = count[c1];
    let same = count[c2];
    if c2 < different + 1 || different + same / 2 < c2 {
        println!("No");
        return;
    }

    println!("Yes");
}

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

B - Sports Festival

最大の人数を変動させるには一番人気のスポーツを潰すしかないので、愚直にやるだけ。

use std::cmp;

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 a: Vec<Vec<usize>> = (0..n)
        .map(|_| (0..m).map(|_| sc.read::<usize>() - 1).collect())
        .collect();

    let mut ans = n;
    let mut pos: Vec<usize> = vec![0; n];
    let mut dead = vec![false; m];
    for _ in 0..m {
        let mut count = vec![0; m];
        for i in 0..n {
            count[a[i][pos[i]]] += 1;
        }
        let (max, max_i) = count
            .iter()
            .enumerate()
            .map(|(i, &c)| (c, i))
            .max()
            .unwrap();
        ans = cmp::min(ans, max);
        dead[max_i] = true;
        for i in 0..n {
            while pos[i] < m && dead[a[i][pos[i]]] {
                pos[i] += 1;
            }
        }
    }
    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()
    }
}

AGC 014 C - Closed Rooms

問題

atcoder.jp

解法

もし、魔法の操作の順序が入れ替わっていて、魔法が「Kこの部屋を選んで解放し、その後、K回移動する」という操作だったら、移動しながら部屋を開けていけば良いので、非常に単純なBFSになる。ここに落とし込むために、操作を以下のように言い換える。

  • 1回目のみ「K回移動する。しまっている部屋には入れない」
  • 2回目以降「K回移動する。どの部屋も入り放題」

もし1回目の操作、すなわちKステップ以内のゴールできれば1を出力する。そうでない場合、Kステップで到達できる点を視点として距離をリセットし、単純にBFSする。

コード

use std::collections::VecDeque;

const INF: u64 = 1e15 as u64;

const DX: [i64; 4] = [0, 0, 1, -1];
const DY: [i64; 4] = [1, -1, 0, 0];

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let k: u64 = sc.read();
    let s: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut dist = vec![vec![INF; w]; h];
    let mut q = VecDeque::new();
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 'S' {
                dist[i][j] = 0;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("1");
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 && s[ni][nj] != '#' && dist[i][j] + 1 <= k {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            if dist[i][j] != INF {
                dist[i][j] = k;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("{}", (dist[i][j] + k - 1) / k);
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }
}

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 132 F - Small Products

問題

atcoder.jp

解法

ナイーブなDPを考えると、遷移する先が区間に分けられ、しかもその区間の数は  O(\sqrt{N})であることに気づく。DPの際に区間ごとにまとめて遷移させれば良い。

コード

use mod_int::ModInt;
use std::collections::BTreeSet;

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

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 mut seg = BTreeSet::new();
    for i in 1.. {
        if i * i > n {
            break;
        }
        let j = i + 1;
        let m = n / j;
        let from = m + 1;
        let to = n / i;

        seg.insert((from, to));
        seg.insert((i, i));
    }

    let seg = seg.into_iter().collect::<Vec<_>>();
    let n = seg.len();
    let mut dp = vec![ModInt::new(1); n];
    for _ in 1..k {
        let mut sum = vec![ModInt::new(0); n + 1];
        for i in 0..n {
            // i -> [0, n-1-i]
            let (from, to) = seg[i];
            let tmp = dp[i] * (to - from + 1);
            sum[n - i] -= tmp;
            sum[0] += tmp;
        }
        let mut next = vec![ModInt::new(0); n];
        let mut cur = ModInt::new(0);
        for i in 0..n {
            cur += sum[i];
            next[i] = cur;
        }
        dp = next;
    }

    let mut ans = ModInt::new(0);
    for i in 0..n {
        let (from, to) = seg[i];
        ans += dp[i] * (to - from + 1);
    }
    println!("{}", ans.0);
}

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

    type Num = usize;

    #[derive(Clone, Copy, Debug)]
    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 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 new(value: Num) -> Self {
            ModInt(value)
        }

        pub fn pow(self, e: usize) -> ModInt<Num> {
            let mut result = ModInt::new(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 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 132 E - Hopscotch Addict

問題

atcoder.jp

解法

ステップが3の倍数でないとゴールできない幅優先探索なので、頂点を3倍に増やせば良い。

コード

use std::collections::VecDeque;

const INF: u64 = std::u64::MAX / 2;

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

    let mut dist = vec![vec![INF; n]; 3];
    dist[0][s] = 0;

    let mut q = VecDeque::new();
    q.push_back((s, 0));
    while let Some((v, step)) = q.pop_front() {
        if v == t && step == 0 {
            println!("{}", dist[step][t] / 3);
            return;
        }
        let next_step = (step + 1) % 3;
        for &next in graph[v].iter() {
            if dist[next_step][next] > dist[step][v] + 1 {
                dist[next_step][next] = dist[step][v] + 1;
                q.push_back((next, next_step));
            }
        }
    }
    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()
    }
}