AtCoder Beginner Contest 263 C

https://atcoder.jp/contests/abc263/tasks/abc263_c

combinationsを使うだけですね。

// Monotonically Increasing
#![allow(non_snake_case)]

use itertools::Itertools;

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 join<T :std::string::ToString>(v: Vec<T>) -> String {
    v.iter().map(|c| c.to_string()).collect::<Vec::<String>>().join(" ")
}

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

fn main() {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    for v in (1..(M+1)).combinations(N) {
        println!("{}", join(v))
    }
}

AtCoder Beginner Contest 264 C

https://atcoder.jp/contests/abc264/tasks/abc264_c

どうしてもインデックスベースになりますね。

// Matrix Reducing
#![allow(non_snake_case)]

use itertools::Itertools;

type Matrix<T> = Vec<Vec<T>>;

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 read_matrix<T: std::str::FromStr>(H: usize) -> Matrix<T> {
    (0..H).map(|_| read_vec()).collect()
}

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

fn read_mat() -> Matrix<i32> {
    let v = read_vec();
    let H: usize = v[0];
    return read_matrix(H);
}

fn slice(A: &Matrix<i32>, is: &Vec<usize>, js: &Vec<usize>) -> Matrix<i32> {
    is.iter().map(|&i| js.iter().map(|&j| A[i][j]).collect()).collect()
}

fn equals(A: &Matrix<i32>, B: &Matrix<i32>) -> bool {
    let H = A.len();
    let W = A[0].len();
    (0..H).all(|i| (0..W).all(|j| A[i][j] == B[i][j]))
}

fn is_reducable(A: Matrix<i32>, B: Matrix<i32>) -> bool {
    let H1 = A.len();
    let W1 = A[0].len();
    let H2 = B.len();
    let W2 = B[0].len();
    for is in (0..H1).combinations(H2) {
        for js in (0..W1).combinations(W2) {
            if equals(&slice(&A, &is, &js), &B) {
                return true
            }
        }
    }
    return false
}

fn main() {
    let A = read_mat();
    let B = read_mat();
    println!("{}", if is_reducable(A, B) { "Yes" } else { "No" })
}

AtCoder Beginner Contest 265 C

https://atcoder.jp/contests/abc265/tasks/abc265_c

こういう問題はOptionを使うとよいようです。1行が少し長くなりますが。
あと、Rustにはloopというキーワードがあるんですね。

// Belt Conveyor
#![allow(non_snake_case)]

use std::collections::HashSet;

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 find_end_point(G: Vec<Vec<char>>) -> Option<(usize, usize)> {
    let H = G.len();
    let W = G[0].len();
    let mut visited = HashSet::<(usize, usize)>::new();
    let mut x = 0usize;
    let mut y = 0usize;
    loop {
        if visited.contains(&(x, y)) {
            return None
        }
        visited.insert((x, y));
        match G[x][y] {
            'U' => { if x == 0     { return Some((x, y)) } else { x -= 1 } },
            'D' => { if x == H - 1 { return Some((x, y)) } else { x += 1 } },
            'L' => { if y == 0     { return Some((x, y)) } else { y -= 1 } },
            'R' => { if y == W - 1 { return Some((x, y)) } else { y += 1 } },
            _         => { return None }
        }
    }
}

fn main() {
    let v = read_vec();
    let H: usize = v[0];
    let G = (0..H).map(|_| read::<String>().chars().collect()).collect();
    match find_end_point(G) {
        Some((x, y)) => { println!("{} {}", x + 1, y + 1) },
        None =>         { println!("{}", -1) }
    }
}

AtCoder Beginner Contest 266 C

https://atcoder.jp/contests/abc266/tasks/abc266_c

各点が凸であることを調べるだけですね。

// Convex Quadrilateral
#![allow(non_snake_case)]

use std::ops::Sub;

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)]
struct Point {
    x: i32,
    y: i32,
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn read() -> Point {
        let v = read_vec();
        Point { x: v[0], y: v[1] }
    }
}


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

fn is_convex(pt1: &Point, pt2: &Point, pt3: &Point) -> bool {
    let v = *pt2 - *pt1;
    let w = *pt3 - *pt2;
    v.x * w.y - v.y * w.x > 0
}

fn is_convex_quad(quad: &Vec<Point>) -> bool {
    (0..4).all(|i| is_convex(&quad[i], &quad[(i+1)&3], &quad[(i+2)&3]))
}

fn main() {
    let quad = (0..4).map(|_| Point::read()).collect();
    let b = is_convex_quad(&quad);
    println!("{}", if b { "Yes" } else { "No" })
}

AtCoder Beginner Contest 267 C

https://atcoder.jp/contests/abc267/tasks/abc267_c

どうしてもusizeとi64の変換が必要な問題なのでめんどうですね。

// Index × A(Continuous ver.)
#![allow(non_snake_case)]

use std::cmp::max;

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 max_sum(M: usize, A: &Vec<i64>) -> i64{
    let N = A.len();
    let mut T: i64 = (0..M).map(|i| A[i]).sum();
    let mut S = (0..M).map(|i| ((i+1) as i64)*A[i]).sum();
    let mut m = S;
    for i in 1..(N-M+1) {
        S = S - T + (M as i64) * A[i+M-1];
        m = max(m, S);
        if i != N - M {
            T = T - A[i-1] + A[i+M-1]
        }
    }
    return m
}

fn main() {
    let v = read_vec();
    let M = v[1];
    let A = read_vec();
    println!("{}", max_sum(M, &A))
}

AtCoder Beginner Contest 268 C

https://atcoder.jp/contests/abc268/tasks/abc268_b

剰余の頻度を集計していますが、めんどうですね。

// Chinese Restaurant
#![allow(non_snake_case)]

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 modulus(n: i32, d: i32) -> i32 {
    let r = n % d;
    if r >= 0 {
        r
    }
    else {
        r + d
    }
}

fn max_num_persons(p: &Vec<i32>) -> i32 {
    let N: usize = p.len();
    let M = N as i32;
    let mut rs: Vec<i32> = (0..N).map(|_| 0).collect();
    for i in 0..N {
        rs[modulus(p[i] - (i as i32), M) as usize] += 1
    }
    (0..N).map(|i| rs[i] + rs[(i+1)%N] + rs[(i+2)%N]).max().unwrap()
}

fn main() {
    let _N: usize = read();
    let p = read_vec();
    println!("{}", max_num_persons(&p))
}

AtCoder Beginner Contest 269 C

https://atcoder.jp/contests/abc269/tasks/abc269_c

ABCのC問題を解いていきます。

Pythonだとgeneratorを使ってこんな感じで書けますが、

def gen_submask(N, L):
    if L == 1:
        yield 0
        if N == 1:
            yield 1
    else:
        L1 = L / 2
        L2 = L - L1
        ns1 = list(gen_submask(N & ((1 << L1) - 1), L1))
        ns2 = list(gen_submask(N >> L1, L2))
        for n2, n1 in product(ns2, ns1):
            yield n1 + (n2 << L1)

RustでIteratorを返すのは難しいので、Vecを返すことにします。

// Submask
#![allow(non_snake_case)]

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 num_digits(n: i64, b: i64) -> i64 {
    if n == 0 { 0 } else { num_digits(n / b, b) + 1 }
}

fn create_submasks(N: i64, L: i64) -> Vec<i64> {
    if L <= 1 {
        (0..(N+1)).collect()
    }
    else {
        let L1 = L / 2;
        let L2 = L - L1;
        let ns1 = create_submasks(N & ((1 << L1) - 1), L1);
        let ns2 = create_submasks(N >> L1, L2);
        let mut ns = Vec::<i64>::new();
        for n2 in ns2.iter() {
            for n1 in ns1.iter() {
                ns.push(n1 + (n2 << L1))
            }
        }
        return ns
    }
}

fn main() {
    let N: i64 = read();
    let L = num_digits(N, 2);
    for n in create_submasks(N, L).iter() {
        println!("{}", n)
    }
}