今日解いた問題

AtCoder Rust 競技プログラミング

問題

atcoder.jp

T経過後の蟻の位置は分かるので、蟻0がどの位置に対応するかを考える。これは座標0を通過した蟻の数で分かる。

コード

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 t: usize = sc.read();
    let xw: Vec<(usize, usize)> = (0..n).map(|_| (sc.read(), sc.read())).collect();

    let mut clockwise = 0;
    let mut counter_clock_wise = 0;
    for (x, w) in xw.iter().cloned() {
        if w == 1 {
            clockwise += (x + t) / l;
        } else if t > x {
            counter_clock_wise += ((l - x) + t - 1) / l;
        }
    }

    let mut next = xw
        .into_iter()
        .map(|(x, w)| {
            if w == 1 {
                (x + t) % l
            } else {
                (l - ((l - x) + t) % l) % l
            }
        })
        .collect::<Vec<_>>();
    next.sort();
    let over = clockwise % n + n - counter_clock_wise % n;
    for i in 0..n {
        println!("{}", next[(i + over) % n]);
    }
}

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

1マス進むと時間が1経過し、時間Kごとに扉を開けてもいいパワーがK部屋分だけ補充されると考える。

コード

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

const INF: i32 = 1e9 as i32;
const DIR: [(i32, i32); 4] = [(0, -1), (0, 1), (-1, 0), (1, 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: i32 = sc.read();
    let board: Vec<_> = (0..h).map(|_| sc.chars()).collect();
    let mut dist = vec![vec![INF; w]; h];

    let mut si = 0;
    let mut sj = 0;
    for i in 0..h {
        for j in 0..w {
            if board[i][j] == 'S' {
                dist[i][j] = 0;
                si = i;
                sj = j;
            }
        }
    }

    let mut q = VecDeque::new();
    q.push_back((0, 0, si, sj));
    for _ in 0.. {
        let mut next_q = VecDeque::new();
        while let Some((time, open, i, j)) = q.pop_front() {
            if i == h - 1 || j == w - 1 || i == 0 || j == 0 {
                let turn = (time + k - 1) / k;
                println!("{}", turn);
                return;
            }
            for (di, dj) in DIR.iter().cloned() {
                let ni = (i as i32) + di;
                let nj = (j as i32) + dj;
                if ni < 0 || nj < 0 {
                    continue;
                }
                let ni = ni as usize;
                let nj = nj as usize;
                if ni >= h || nj >= w {
                    continue;
                }

                if board[ni][nj] == '#' && open > 0 && dist[ni][nj] > time + 1 {
                    dist[ni][nj] = time + 1;
                    if (time + 1) % k == 0 {
                        next_q.push_back((time + 1, k, ni, nj));
                    } else {
                        q.push_back((time + 1, open - 1, ni, nj));
                    }
                } else if board[ni][nj] == '.' && dist[ni][nj] > time + 1 {
                    dist[ni][nj] = time + 1;
                    if (time + 1) % k == 0 {
                        next_q.push_back((time + 1, k, ni, nj));
                    } else {
                        q.push_back((time + 1, open, ni, nj));
                    }
                }
            }

            let next_time = (time + k) / k * k;
            next_q.push_front((next_time, k, i, j));
        }
        q = next_q;
    }
}

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

解説動画のとおりにやった。

1 ... a-1, a+1, ... , x
1 ... b-1, b+1, ... , x

という2つのほぼ等差数列から作れる積の最大値が ab を超えないような x を二分探索する。

コード

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let q: usize = sc.read();
    for _ in 0..q {
        let a: usize = sc.read();
        let b: usize = sc.read();
        let (a, b) = if a > b { (b, a) } else { (a, b) };

        let mut ok = a - 1;
        let mut ng = 1e10 as usize;
        while ng - ok > 1 {
            let x = (ok + ng) / 2;
            let mut max = 0;
            if x >= b - 1 {
                // 1 ... a-1    a+1   ... x-b+1 x-b+2 ... x
                // x ... x-a+2  x-a+1 ... b+1   b-1   ... 1
                max = get_max(1, a - 1, x, x + 2 - a);
                max = cmp::max(max, get_max(a + 1, x - (b - 1), x - (a - 1), b + 1));
                max = cmp::max(max, get_max(x + 2 - b, x, b - 1, 1));
            } else {
                // 1 ... a-1      a+1 ... x
                // x-1 ... x-a+1  x-a ... 1
                max = get_max(1, a - 1, x - 1, x - (a - 1));
                max = cmp::max(max, get_max(a + 1, x, x - a, 1));
            }

            if max < a * b {
                ok = x;
            } else {
                ng = x;
            }
        }
        println!("{}", if a <= ok { ok - 1 } else { ok });
    }
}

fn get_max(from_a: usize, to_a: usize, from_b: usize, to_b: usize) -> usize {
    if from_a > to_a {
        return 0;
    }
    assert_eq!(to_a + 1 - from_a, from_b + 1 - to_b);
    let mut m = (from_a + from_b) / 2;
    let mut max = cmp::max(from_a * from_b, to_a * to_b);
    if from_a <= m && m <= to_a {
        let da = m - from_a;
        let b = from_b - da;
        max = cmp::max(max, m * b);
    }
    m += 1;
    if from_a <= m && m <= to_a {
        let da = m - from_a;
        let b = from_b - da;
        max = cmp::max(max, m * b);
    }
    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' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .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.jp

すごく有名なパズル。

コード

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 board: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut blue = vec![vec!['.'; w]; h];
    let mut red = vec![vec!['.'; w]; h];
    for i in 0..h {
        for j in 0..w {
            if j == 0 {
                red[i][j] = '#';
            } else if j == w - 1 {
                blue[i][j] = '#';
            } else if i % 2 == 0 {
                red[i][j] = '#';
            } else {
                blue[i][j] = '#';
            }

            if board[i][j] == '#' {
                red[i][j] = '#';
                blue[i][j] = '#';
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            print!("{}", red[i][j]);
        }
        println!();
    }
    println!();
    for i in 0..h {
        for j in 0..w {
            print!("{}", blue[i][j]);
        }
        println!();
    }
}

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

上に重ねて色が塗られるので、クエリを逆から見ていく。

コード

use std::collections::VecDeque;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let m: usize = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }
    let q: usize = sc.read();
    let mut potential = vec![-1; n];
    let mut color = vec![0; n];
    let vdc: Vec<_> = (0..q)
        .map(|_| (sc.read::<usize>() - 1, sc.read::<i64>(), sc.read::<usize>()))
        .collect();

    for (root, distance, c) in vdc.into_iter().rev() {
        if potential[root] >= distance {
            continue;
        }
        let mut q = VecDeque::new();
        q.push_back(root);
        if color[root] == 0 {
            color[root] = c;
        }
        potential[root] = distance;
        while let Some(v) = q.pop_front() {
            if potential[v] == 0 {
                continue;
            }
            for &next in graph[v].iter() {
                if color[next] == 0 {
                    color[next] = c;
                }
                if potential[next] < potential[v] - 1 {
                    potential[next] = potential[v] - 1;
                    q.push_back(next);
                }
            }
        }
    }

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

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