今日復習した問題

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