AtCoder Beginner Contest 303 D

https://atcoder.jp/contests/abc303/tasks/abc303_d

Caps LockがOffとOnの2状態でDPします。

// Shift vs. CapsLock
#![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()
}

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


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

fn read_input() -> (u64, u64, u64, String) {
    let v = read_vec();
    let X = v[0];
    let Y = v[1];
    let Z = v[2];
    let S = read();
    (X, Y, Z, S)
}

fn f(X: u64, Y: u64, Z: u64, S: String) -> u64 {
    let L = S.len();
    let mut v: Vec<(u64, u64)> = (0..L+1).map(|_| (0, 0)).collect();
    for (i, c) in S.chars().enumerate() {
        if c == 'a' {
            let Off = if i == 0 { X } else { min(v[i].0, v[i].1 + Z) + X };
            let On = if i == 0 { Z + Y } else { min(v[i].0 + Z, v[i].1) + Y };
            v[i+1] = (Off, On)
        }
        else {
            let Off = if i == 0 { Y } else { min(v[i].0, v[i].1 + Z) + Y };
            let On = if i == 0 { Z + X } else { min(v[i].0 + Z, v[i].1) + X };
            v[i+1] = (Off, On)
        }
    }
    min(v[L].0, v[L].1)
}


//////////////////// main ////////////////////

fn main() {
    let (X, Y, Z, S) = read_input();
    println!("{}", f(X, Y, Z, S))
}

アルゴリズムと数学 062

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

全く予期していなかったのですが、この問題の解法は問題59と完全に同じです。この問題も、ある状態から一意に次の状態に進むことができますが、後ろに一意に戻れるかわかりません。
このため、前に進むことができるProceedableというTraitを定義して、これを実装していれば問題が解ける関数を作りました。問題59はu64がこのTraitを次のように実装するだけです。

impl Proceedable for u64 {
    fn proceed(&self) -> Self {
        self * 2 % 10
    }
}

// Teleporter
#![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()
}

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


//////////////////// Proceedable ////////////////////

trait Proceedable {
    fn proceed(&self) -> Self;
}

fn proceed_length<T: Proceedable>(e: T, n: usize) -> T {
    let mut s = e;
    for _ in 0..n {
        s = s.proceed()
    }
    s
}

fn find_period<T: Proceedable + PartialEq + Copy>(init: T) -> usize {
    let mut e1 = init;
    let mut e2 = init;
    for i in 1..  {
        e1 = proceed_length(e1, 1);
        e2 = proceed_length(e2, 2);
        if e1 == e2 {
            return i
        }
    }
    0
}

fn proceed_long<T: Proceedable + PartialEq + Copy>(init: T, n: usize) -> T {
    let period = find_period(init);
    let length = min(n, n % period + period);
    proceed_length(init, length)
}


//////////////////// State ////////////////////

type City = usize;

#[derive(Clone, Copy, PartialEq)]
struct State<'a> {
    city: usize,
    A: &'a Vec<City>
}

impl Proceedable for State<'_> {
    fn proceed(&self) -> Self {
        State { city: self.A[self.city-1], A: self.A }
    }
}


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

fn read_input() -> (usize, Vec<City>) {
    let v = read_vec();
    let K = v[1];
    let A: Vec<City> = read_vec();
    (K, A)
}

fn f(K: usize, A: Vec<City>) -> City {
    let init = State { city: 1, A: &A };
    let state = proceed_long(init, K);
    state.city
}

fn main() {
    let (K, A) = read_input();
    println!("{}", f(K, A))
}

アルゴリズムと数学 061

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

ある状態について、次の状態が全て必勝ならその状態は必敗、次の状態に一つでも必敗があれば必勝です。
1は必敗、2は次の状態の1が必敗なので必勝、3は次の状態の2が必勝なので必敗、4～6は次の状態に3が含まれているので必勝、7は次の状態が4～6なので必敗、8～14は次の状態に7が含まれているので必勝、15は次の状態が8～14なので必敗、と考えていくと、2進法で全ての桁が1のときに必敗、そうでないときは必勝であることが分かります。

// Stones Game 2
#![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()
}


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

fn is_one_only(N: u64) -> bool {
    if N == 1 {
        true
    }
    else if N % 2 == 0 {
        false
    }
    else {
        is_one_only(N >> 1)
    }
}

fn f(N: u64) {
    if is_one_only(N) {
        println!("Second")
    }
    else {
        println!("First")
    }
}

fn main() {
    let N = read();
    f(N)
}

アルゴリズムと数学 060

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

4の剰余を取るだけですね。

// Stones Game 1
#![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()
}


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

fn f(N: u64) {
    if N % 4 != 0 {
        println!("First")
    }
    else {
        println!("Second")
    }
}

fn main() {
    let N = read();
    f(N)
}

アルゴリズムと数学 059

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

べき乗の計算をするだけですが、それでは芸がないので、周期を求めます。こうすると計算量が減る可能性があります。2のべきで10の剰余を取りますが、2と10が互いに素でないので、べき乗していっても純粋なループにはなりません。互いに素なら純粋なループになります。例えば、2と5なら、

1 -> 2 -> 4 -> 3 -> 1

とループになります。しかし、互いに素でないと後ろには一意にたどれないので、純粋なループになりません。例えば、2と10なら、

1 -> 2 <- 6

となります。ただ、進む方向には一意に決まるので、いつか一度来た値に戻ります。そのため、ρの字になります。

1 -> 2 -> 4
     ↑   ↓
     6 <- 8

このとき、周期を求めるメモリを使わない方法があります。1歩ずつ進むのと2歩ずつ進むのを比較して同じになったら、1歩ずつ進んだ方が周期分進んでいます。ただ、周期しかわからず、どこからループになるかはわかりません。

// Power of Two
#![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 find_period(a: u64, d: u64) -> u64 {
    let mut b = 1;
    let mut c = 1;
    for i in 1..  {
        b = b * a % d;
        c = c * a * a % d;
        if b == c {
            return i
        }
    }
    0
}

fn pow_mod(a: u64, e: u64, d: u64) -> u64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        a
    }
    else if e % 2 == 0 {
        let b = pow_mod(a, e/2, d);
        b * b % d
    }
    else {
        pow_mod(a, e-1, d) * a % d
    }
}

fn f(N: u64) -> u64 {
    let period = find_period(2, 10);
    let length = min(N, N % period + period);
    pow_mod(2, length, 10)
}

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

アルゴリズムと数学 058

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

届くかと偶奇の判定だけですね。

// Move on Squares 1
#![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()
}

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


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

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

fn f(N: i64, X: i64, Y: i64) -> bool {
    N >= X.abs() + Y.abs() && (X + Y - N) % 2 == 0
}

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

AtCoder Beginner Contest 302 E

https://atcoder.jp/contests/abc302/tasks/abc302_e

Queryをenumにして、matchで分けるときれいに書けますね。
HashMapでborrowするとややこしいことになりますね。

// Isolation
#![allow(non_snake_case)]

use std::collections::{HashMap, 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()
}

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

fn read_input() -> (usize, usize) {
    let v = read_vec();
    let N = v[0];
    let Q = v[1];
    (N, Q)
}

type Node = usize;
type Graph = HashMap<Node, HashSet<Node>>;

enum Query {
    Add(usize, Node, Node),
    Remove(usize, Node)
}

fn read_query() -> Query {
    let v = read_vec();
    if v[0] == 1 {
        Query::Add(v[0], v[1], v[2])
    }
    else {
        Query::Remove(v[0], v[1])
    }
}

fn add_edge(v: Node, w: Node, graph: &mut Graph) -> usize {
    let e1 = graph.entry(v).or_insert(HashSet::new());
    e1.insert(w);
    let num1 = if e1.len() == 1 { 1 } else { 0 };
    let e2 = graph.entry(w).or_insert(HashSet::new());
    e2.insert(v);
    let num2 = if e2.len() == 1 { 1 } else { 0 };
    num1 + num2
}

fn remove_node(v: Node, graph: &mut Graph) -> usize {
    let op = graph.get(&v);
    if op.is_none() {
        return 0
    }
    
    let s = op.unwrap();
    if s.is_empty() {
        return 0
    }
    
    let num = s.iter().filter(|w| graph.get(w).unwrap().len() == 1).count();
    let neighbors: Vec<Node> = s.iter().map(|&w| w).collect();
    for w in neighbors.iter() {
        graph.get_mut(w).unwrap().remove(&v);
    }
    let s1 = graph.get_mut(&v).unwrap();
    s1.clear();
    num + 1
}

fn f(N: usize, Q: usize) {
    let mut graph: Graph = Graph::new();
    let mut num_isolated = N;
    for _ in 0..Q {
        match read_query() {
            Query::Add(_, v, w) => {
                num_isolated -= add_edge(v, w, &mut graph)
            },
            Query::Remove(_, v) => {
                num_isolated += remove_node(v, &mut graph)
            }
        }
        println!("{}", num_isolated)
    }
}

//////////////////// main ////////////////////

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