AtCoder Beginner Contest 299 E

https://atcoder.jp/contests/abc299/tasks/abc299_e

最初に全部黒にして、dより内側は全て白くします。そこで、dのところが全て白でないかを調べます。簡単そうですが、トラップがあります。

// Nearest Black Vertex
#![allow(non_snake_case)]

use std::collections::{VecDeque, HashSet, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

struct Graph {
    g: Vec<Vec<usize>>
}

impl Graph {
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<usize>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push(w);
            g[w].push(v)
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>, Vec<(usize, usize)>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<Edge> = (0..M).map(|_| read_vec::<Node>()).
                                    map(|v| (v[0]-1, v[1]-1)).collect();
    let K: usize = read();
    let mins: Vec<(usize, usize)> = (0..K).map(|_| read_vec::<usize>()).
                                            map(|v| (v[0]-1, v[1])).collect();
    (N, edges, mins)
}

fn is_duplicated(mins: &Vec<(usize, usize)>) -> bool {
    let mut m: HashMap<usize, usize> = HashMap::new();
    for &(v, d) in mins.iter() {
        if let Some(value) = m.get_mut(&v) {
            if *value != v {
                return true
            }
        }
        else {
            m.insert(v, d);
        }
    }
    false
}

fn create_distances(v0: Node, d: usize, graph: &Graph) -> Vec<(Node, usize)> {
    let mut dists: Vec<(Node, usize)> = Vec::new();
    let mut queue = VecDeque::new();
    let mut visited: HashSet<Node> = HashSet::new();
    dists.push((v0, 0));
    queue.push_back((v0, 0usize));
    visited.insert(v0);
    while !queue.is_empty() {
        let (v1, d1) = queue.pop_front().unwrap();
        if d1 == d {
            continue
        }
        
        for v2 in graph.g[v1].iter() {
            if !visited.contains(v2) {
                dists.push((*v2, d1 + 1));
                queue.push_back((*v2, d1 + 1));
                visited.insert(*v2);
            }
        }
    }
    dists
}

fn create_equations_and_inequations(
                table: Vec<(usize, Vec<(Node, usize)>)>, N: usize
                                    ) -> (Vec<i32>, Vec<Vec<Node>>) {
    let mut equations: Vec<i32> = (0..N).map(|_| 1).collect();
    let mut inequations: Vec<Vec<Node>> = Vec::new();
    for (max_d, dists) in table.into_iter() {
        let mut inequation: Vec<Node> = Vec::new();
        for (v1, d) in dists.into_iter() {
            if d < max_d {
                equations[v1] = 0
            }
            else {
                inequation.push(v1)
            }
        }
        inequations.push(inequation)
    }
    (equations, inequations)
}

fn conflicts(inequations: Vec<Vec<Node>>, equations: &Vec<i32>) -> bool {
    for v in inequations.into_iter() {
        if v.into_iter().all(|i| equations[i] == 0) {
            return true
        }
    }
    false
}

fn f(N: usize, edges: Vec<Edge>, mins: Vec<(usize, usize)>) {
    if is_duplicated(&mins) {
        println!("No");
        return
    }
    
    let graph = Graph::create_from_edges(N, edges);
    let table: Vec<(usize, Vec<(Node, usize)>)> =
                    mins.into_iter().
                    map(|(v0, d)| (d, create_distances(v0, d, &graph))).
                    collect();
    let (equations, inequations) = create_equations_and_inequations(table, N);
    if conflicts(inequations, &equations) {
        println!("No")
    }
    else {
        let s = equations.iter().map(|n| n.to_string()).
                                collect::<Vec<String>>().join("");
        println!("Yes");
        println!("{}", s)
    }
}

fn main() {
    let (N, edges, mins) = read_input();
    f(N, edges, mins)
}

AtCoder Beginner Contest 299 D

https://atcoder.jp/contests/abc299/tasks/abc299_d

最初が0で最後が1と決まっているのがポイントですね。あとは二分探索で。

// Find by Query
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn get_char(pos: i32) -> i32 {
    println!("? {}", pos);
    read()
}

fn bin_search(pos1: i32, pos2: i32, chr1: i32) -> i32 {
    if pos2 - pos1 == 1 {
        pos1
    }
    else {
        let mid = (pos1 + pos2) / 2;
        let chr_mid = get_char(mid);
        if chr_mid != chr1 {
            bin_search(pos1, mid, chr1)
        }
        else {
            bin_search(mid, pos2, chr_mid)
        }
    }
}

fn main() {
    let N: i32 = read();
    println!("! {}", bin_search(1, N, 0));
}

アルゴリズムと数学 047

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ao

グラフをたどるだけですね。

// Bipartite Graph
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

struct Graph {
    g: Vec<Vec<usize>>
}

impl Graph {
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<usize>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push(w);
            g[w].push(v)
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<Edge> = (0..M).map(|_| read_vec::<Node>()).
                                    map(|w| (w[0]-1, w[1]-1)).collect();
    (N, edges)
}

fn f(N: usize, edges: Vec<Edge>) -> bool {
    let graph = Graph::create_from_edges(N, edges);
    let mut colors: Vec<i32> = (0..N).map(|_| 0).collect();
    let mut unvisited: HashSet<Node> = (0..N).collect();
    
    while !unvisited.is_empty() {
        let v0 = unvisited.iter().next().unwrap();
        let mut stack: Vec<usize> = vec![*v0];
        while !stack.is_empty() {
            let v = stack.pop().unwrap();
            unvisited.remove(&v);
            for w in graph.g[v].iter() {
                if colors[*w] == 0 {
                    colors[*w] = if colors[v] == 1 { 2 } else { 1 };
                    stack.push(*w)
                }
                else if colors[*w] == colors[v] {
                    return false
                }
            }
        }
    }
    true
}

fn main() {
    let (N, edges) = read_input();
    println!("{}", YesNo(f(N, edges)))
}

アルゴリズムと数学 046

https://atcoder.jp/contests/math-and-algorithm/tasks/abc007_3

PointをGenericを使って書くととたんに難しくなりますね。
幅優先探索のQueueは、VecDequeを使います。

// 幅優先探索
#![allow(non_snake_case)]

use std::ops::{Add, Sub};
use std::collections::{VecDeque, HashSet};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(Eq, Hash, PartialEq)]
#[derive(Debug)]
struct Point<T> {
    x: T,
    y: T,
}

impl<T: std::fmt::Display> Point<T> {
    fn new(x: T, y: T) -> Self {
        Self { x, y }
    }
}

impl<T> Add for Point<T>
    where T: std::ops::Add<Output = T> + Copy {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl<T> Sub for Point<T>
    where T: std::ops::Sub<Output = T> + Copy {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl<T: std::str::FromStr + Copy> Point<T> {
    fn read() -> Point<T> {
        let v: Vec<T> = read_vec();
        Point::<T> { x: v[0], y: v[1] }
    }
}


//////////////////// Maze ////////////////////

struct Maze {
    m: Vec<Vec<char>>
}

impl Maze {
    fn width(&self) -> usize {
        self.m[0].len()
    }
    
    fn height(&self) -> usize {
        self.m.len()
    }
    
    fn is_accessible(&self, x: usize, y: usize) -> bool {
        if x < 0 || x >= self.width() || y < 0 || y >= self.height() {
            false
        }
        else {
            self.m[y][x] == '.'
        }
    }
    
    fn read(R: usize) -> Maze {
        let m = (0..R).map(|_| read::<String>()).
                        map(|s| s.chars().collect::<Vec<char>>()).
                        collect::<Vec<Vec<char>>>();
        Maze { m }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Maze, Point<i32>, Point<i32>) {
    let v = read_vec();
    let R: usize = v[0];
    let start = Point::<i32>::read() - Point::<i32> { x: 1, y: 1 };
    let goal = Point::<i32>::read() - Point::<i32> { x: 1, y: 1 };
    let maze = Maze::read(R);
    (maze, start, goal)
}

fn is_accessible(pt: Point<i32>, maze: &Maze) -> bool {
    maze.is_accessible(pt.y as usize, pt.x as usize)
}

fn f(maze: Maze, start: Point<i32>, goal: Point<i32>) -> i32 {
    let steps: Vec<Point<i32>> = vec![(1, 0), (0, 1), (-1, 0), (0, -1)].
                iter().map(|(x, y)| Point::<i32>::new(*x, *y)).collect();
    let mut queue = VecDeque::new();
    queue.push_back((start, 0i32));
    let mut visited: HashSet<Point<i32>> = HashSet::new();
    visited.insert(start);
    loop {
        let (pt0, num_steps) = queue.pop_front().unwrap();
        if pt0 == goal {
            return num_steps
        }
        
        for step in steps.iter() {
            let pt = pt0 + *step;
            if is_accessible(pt, &maze) && !visited.contains(&pt) {
                queue.push_back((pt, num_steps + 1));
                visited.insert(pt);
            }
        }
    }
}

fn main() {
    let (maze, start, goal) = read_input();
    println!("{}", f(maze, start, goal))
}

AtCoder Beginner Contest 298 E

https://atcoder.jp/contests/abc298/tasks/abc298_e

単なるDPですが、Dを法とした逆数を求めなければなりません。拡張ユークリッド互除法ですね。一度書けば終わりですが。

// Unfair Sugoroku
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// constants ////////////////////

const D: usize = 998244353;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize, usize, usize, usize) {
    let v = read_vec();
    (v[0], v[1], v[2], v[3], v[4])
}

fn f(N: usize, A: usize, B: usize, P: usize, Q: usize) -> usize {
    let inv_P = inverse(P as i64, D as i64) as usize;
    let inv_Q = inverse(Q as i64, D as i64) as usize;
    
    let mut dp1: Vec<Vec<usize>>
                = (0..N+1).map(|_| (0..N+1).map(|_| 0).collect()).collect();
    let mut dp2 = dp1.to_vec();
    dp2[A][B] = 1;
    let mut win: usize = 0;
    for x in A..N {
        for y in B..N {
            for i in 1..P+1 {
                let x1 = min(x + i, N);
                let p = dp2[x][y] * inv_P % D;
                dp1[x1][y] = (dp1[x1][y] + p) % D;
                if x1 == N {
                    win += p
                }
            }
            for i in 1..Q+1 {
                let y1 = min(y + i, N);
                let p = dp1[x][y] * inv_Q % D;
                dp2[x][y1] = (dp2[x][y1] + p) % D;
            }
        }
    }
    win % D
}

fn main() {
    let (N, A, B, P, Q) = read_input();
    println!("{}", f(N, A, B, P, Q))
}

AtCoder Beginner Contest 298 D

https://atcoder.jp/contests/abc298/tasks/abc298_d

剰余を用意して、1なら10倍して足して、2なら数字×10のべき乗を引けばいいのですが、Rustには負数の剰余を取ると負になるというトラップがありますね。

// Writing a Numeral
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 998244353;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn create_pows(b: i64, n: i32) -> Vec<i64> {
    let mut pows: Vec<i64> = (0..n).map(|_| 1).collect();
    for i in 1..(n as usize) {
        pows[i] = pows[i-1] * b % D
    }
    pows
}

fn f(Q: i32) {
    let mut a: Vec<i64> = (0..Q+1).map(|_| 1).collect();
    let pows: Vec<i64> = create_pows(10, Q+1);
    let mut first: usize = 0;
    let mut last: usize = 1;
    let mut n: i64 = 1;
    for _ in 0..Q {
        let v: Vec<i64> = read_vec();
        if v[0] == 1 {
            a[last] = v[1];
            n = (n * 10 + v[1]) % D;
            last += 1
        }
        else if v[0] == 2 {
            n = (n - a[first] * pows[last-first-1]) % D;
            if n < 0 {
                n += D
            }
            first += 1
        }
        else {
            println!("{}", n);
        }
    }
}

fn main() {
    let Q: i32 = read();
    f(Q)
}

アルゴリズムと数学 045

https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_bz

そのままですね。
RustのIteratorにはcountがあるのがいいですね。

// Easy Graph Problem
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

struct Graph {
    g: Vec<Vec<Node>>
}

impl Graph {
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<Node>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push(w);
            g[w].push(v)
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<Edge> = (0..M).map(|_| read_vec::<Node>()).
                                    map(|u| (u[0]-1, u[1]-1)).collect();
    (N, edges)
}

fn is_valid_node(v: Node, graph: &Graph) -> bool {
    graph.g[v].iter().filter(|w| *w < &v).count() == 1
}

fn f(N: usize, edges: Vec<Edge>) -> usize {
    let graph = Graph::create_from_edges(N, edges);
    (0..N).filter(|v| is_valid_node(*v, &graph)).count()
}

fn main() {
    let (N, edges) = read_input();
    println!("{}", f(N, edges))
}