2019-07-16

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

AOJ Rust 動的計画法

問題

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

解法

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

2019-07-04

ICFP Contest 2019 振り返りメモ

osak.hatenablog.jp

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

雑感

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

2019-07-01

今日復習した問題

AtCoder 競技プログラミング Rust

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

2019-06-30

AGC 014 C - Closed Rooms

AtCoder Rust 競技プログラミング

問題

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

2019-06-29

AtCoder Beginner Contest 132 F - Small Products

AtCoder Rust 競技プログラミング

問題

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

2019-06-29

AtCoder Beginner Contest 132 E - Hopscotch Addict

AtCoder Rust 競技プログラミング

問題

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

2019-06-29

AtCoder Beginner Contest 132 D - Blue and Red Balls

AtCoder 競技プログラミング Rust

問題

atcoder.jp

解法

K個の青いボールをi個の区間に分け、かつ、全ての区間が1個以上ボールを含むような青いボールの分け方は $_{(K-i)+i-1}C_{K-i}$ である。同様に考えて赤いボールの分け方を求め、この2つの積が答えになる。

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 blue_ball: usize = sc.read();
    let c = Combination::new(n * 2 + 1, MOD);

    let red_ball = n - blue_ball;
    for seg in 1..(blue_ball + 1) {
        if seg > blue_ball || seg - 1 > red_ball {
            println!("0");
            continue;
        }
        let free_blue = blue_ball - seg;
        let free_red = red_ball - (seg - 1);
        let ans = c.get(free_blue + seg - 1, free_blue) * c.get(free_red + seg + 1 - 1, free_red);
        println!("{}", ans % MOD);
    }
}

pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Combination {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Combination {
            fact: fact,
            inv_fact: inv_fact,
            modulo: modulo,
        }
    }

    pub fn get(&self, x: usize, y: usize) -> usize {
        assert!(x >= y);
        self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
    }

    pub fn h(&self, n: usize, r: usize) -> usize {
        self.get(n + r - 1, r)
    }
}

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