AtCoder Beginner Contest 342 F

https://atcoder.jp/contests/abc342/tasks/abc342_f

まず最終的にyがいくつになるかの確率を求めて、自分の勝つ確率を求めます。そこでやめたときの勝つ確率と、サイコロを振ったときの勝つ確率を求めます。

// Black Jack
#![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() -> (usize, usize, usize) {
    let v: Vec<usize> = read_vec();
    let (N, L, D) = (v[0], v[1], v[2]);
    (N, L, D)
}

fn calc_dealder(L: usize, D: usize) -> Vec<f64> {
    let mut acc: Vec<f64> = vec![0.0; L+D+1];
    acc[1] = 1.0;
    for i in 1..L+1 {
        let first = if i < D { 0 } else { i - D };
        acc[i+1] = acc[i] + (acc[i] - acc[first]) / (D as f64)
    }
    for i in L+1..L+D {
        let first = if i < D { 0 } else { i - D };
        acc[i+1] = acc[i] + (acc[L] - acc[first]) / (D as f64)
    }
    for i in L+1..L+D+1 {
        acc[i] -= acc[L]
    }
    for i in 1..L+1 {
        acc[i] = 0.0
    }
    acc
}

fn F(N: usize, L: usize, D: usize) -> f64 {
    let acc_dealer = calc_dealder(L, D);
    let accumulate = |first, last| -> f64 {
        if first > L+D {
            0.0
        }
        else {
            acc_dealer[min(last, L+D)] - acc_dealer[first]
        }
    };
    
    let mut acc_win: Vec<f64> = vec![0.0; N+2];
    for x in (0..N+1).rev() {
        // やめた場合
        let p1 = 1.0 - accumulate(x, N+1);
        // 続けた場合
        let p2 = (acc_win[x+1] - acc_win[min(N+1, x+D+1)]) / (D as f64);
        acc_win[x] = acc_win[x+1] + f64::max(p1, p2);
    }
    acc_win[0] - acc_win[1]
}

fn main() {
    let (N, L, D) = read_input();
    println!("{}", F(N, L, D))
}

AtCoder Beginner Contest 342 E

https://atcoder.jp/contests/abc342/tasks/abc342_e

逆から考えれば単なるダイクストラです。

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


//////////////////// TimeTable ////////////////////

type Time = i64;
type Node = usize;

#[derive(Clone)]
struct TimeTable {
    l: Time,
    d: Time,
    k: Time,
    c: Time,
    A: Node,
    B: Node
}

impl TimeTable {
    fn latest_start_time(&self, t0: Time) -> Option<Time> {
        if t0 < self.c + self.l + self.d {
            None
        }
        else {
            let i = min(self.k-1, (t0 - self.c - self.l) / self.d);
            Some(self.l + i * self.d)
        }
    }
    
    fn read() -> TimeTable {
        let v = read_vec();
        let (l, d, k, c) = (v[0], v[1], v[2], v[3]);
        let (A, B) = ((v[4] - 1) as Node, (v[5] - 1) as Node);
        TimeTable { l, d, k, c, A, B }
    }
}


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

struct Graph {
    vs: Vec<Vec<TimeTable>>
}

impl Graph {
    fn neighbors(&self, v0: Node, t0: Time) -> Vec<(Node, Time)> {
        let mut neighs: Vec<(Node, Time)> = vec![];
        for timetable in self.vs[v0].iter() {
            if let Some(t) = timetable.latest_start_time(t0) {
                neighs.push((timetable.A, t))
            }
        }
        neighs
    }
    
    fn create(N: usize, timetables: Vec<TimeTable>) -> Graph {
        let mut vs: Vec<Vec<TimeTable>> = vec![vec![]; N];
        for time in timetables.into_iter() {
            vs[time.B].push(time)
        }
        Graph { vs }
    }
}


//////////////////// Dijkstra ////////////////////

const INF: Time = 10_i64.pow(18)*2;

use std::collections::BinaryHeap;

#[derive(Debug, Eq, PartialEq)]
struct Item {
    time: Time,
    node: Node,
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.time.cmp(&other.time)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn Dijkstra(graph: Graph, v0: Node) -> Vec<Time> {
    let N = graph.vs.len();
    let mut times: Vec<Time> = vec![0; N];
    let mut heap = BinaryHeap::new();
    heap.push(Item { time: INF, node: v0 });
    while let Some(v) = heap.pop() {
        if times[v.node] != 0 {
            continue
        }
        
        times[v.node] = v.time;
        let neis = graph.neighbors(v.node, v.time);
        for (v2, t2) in neis.into_iter() {
            if times[v2] == 0 {
                heap.push(Item { time: t2, node: v2 })
            }
        }
    }
    times
}


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

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

fn F(N: usize, timetables: Vec<TimeTable>) {
    let graph = Graph::create(N, timetables);
    let times = Dijkstra(graph, N-1);
    for i in 0..N-1 {
        if times[i] != 0 {
            println!("{}", times[i])
        }
        else {
            println!("Unreachable")
        }
    }
}

fn main() {
    let (N, timetables) = read_input();
    F(N, timetables)
}

AtCoder Beginner Contest 342 D

https://atcoder.jp/contests/abc342/tasks/abc342_d

基本的には、素因数分解して、指数が奇数の素数だけ残して、同じものを数えればよいです。

// Square Pair
#![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 div_pow(n: u32, d: u32) -> (u32, u32) {
    let mut e: u32 = 0;
    let mut m = n;
    while m % d == 0 {
        e += 1;
        m /= d
    }
    (e, m)
}


//////////////////// Factors ////////////////////

struct Factors {
    fs: Vec<(u32, u32)>
}

impl Factors {
    fn make_min_prime_table(N: usize) -> Vec<u32> {
        let mut a: Vec<u32> = (0..N+1).map(|n| n as u32).collect();
        let mut b: Vec<u32> = vec![1_u32; N+1];
        for p in (2..).take_while(|&p| p*p <= N) {
            if a[p] == 1 {
                continue
            }
            for n in (p..N+1).step_by(p) {
                let (_, m) = div_pow(a[n], p as u32);
                a[n] = m;
                if b[n] == 1 {
                    b[n] = p as u32
                }
            }
        }
        
        for n in 2..N+1 {
            if a[n] > 1 {
                b[n] = a[n]
            }
        }
        b
    }
    
    fn factorize(n: u32, table: &Vec<u32>) -> Factors {
        if n == 1 {
            return Factors { fs: vec![] }
        }
        
        let p = table[n as usize];
        let (e, m) = div_pow(n, p);
        let fs1 = Factors { fs: vec![(p, e)] };
        let fs2 = Factors::factorize(m, table);
        fs1 * fs2
    }
}

use std::ops::Mul;

impl Mul for Factors {
    type Output = Self;
    
    fn mul(self, other: Self) -> Self {
        let mut fs = self.fs.to_vec();
        for &a in other.fs.iter() {
            fs.push(a)
        }
        Self { fs }
    }
}


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

fn read_input() -> Vec<u32> {
    let _N: usize = read();
    let A: Vec<u32> = read_vec();
    A
}

fn not_square(n: u32, table: &Vec<u32>) -> u32 {
    if n <= 3 {
        return n
    }
    
    let fs = Factors::factorize(n, table);
    let ps: Vec<u32> = fs.fs.into_iter().filter(|&(_, e)| e % 2 == 1).
                                            map(|(p, _)| p).collect();
    ps.into_iter().fold(1, |x, y| x*y)
}

use std::collections::HashMap;

fn count(B: Vec<u32>) -> HashMap<u32, usize> {
    let mut c: HashMap<u32, usize> = HashMap::new();
    for b in B.into_iter() {
        let e = c.entry(b).or_insert(0);
        (*e) += 1
    }
    c
}

fn F(A: Vec<u32>) -> usize {
    let N = A.len();
    let max_value = A.iter().map(|&n| n).max().unwrap();
    let table = Factors::make_min_prime_table(max_value as usize);
    let B: Vec<u32> = A.iter().map(|&n| not_square(n, &table)).collect();
    let c = count(B);
    let mut s = 0;
    for (m, f) in c.into_iter() {
        if m == 0 {
            s += f*N - f*(f+1)/2
        }
        else {
            s += f*(f-1)/2
        }
    }
    s
}

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

MojoでProject Euler 17

https://projecteuler.net/problem=17

Mojoには、

let v = ["one", "two", ...]

みたいなのがあるにはあるんですが、これはListLiteralといって、要素にアクセスするにはタプルと同じように、

print(v.get[1, StringLiteral]())

コンパイル時にインデックスを指定しなければならないので、使えないです。
分岐するよりはましなので、push_backを使っています。

import sys


#################### process ####################

var v1 = DynamicVector[StringLiteral]()
var v2 = DynamicVector[StringLiteral]()
var v3 = DynamicVector[StringLiteral]()

fn push_to_v1():
    v1.push_back("one")
    v1.push_back("two")
    v1.push_back("three")
    v1.push_back("four")
    v1.push_back("five")
    v1.push_back("six")
    v1.push_back("seven")
    v1.push_back("eight")
    v1.push_back("nine")
    v1.push_back("ten")

fn push_to_v2():
    v2.push_back("eleven")
    v2.push_back("twelve")
    v2.push_back("thirteen")
    v2.push_back("fourteen")
    v2.push_back("fifteen")
    v2.push_back("sixteen")
    v2.push_back("seventeen")
    v2.push_back("eighteen")
    v2.push_back("nineteen")

fn push_to_v3():
    v3.push_back("twenty")
    v3.push_back("thirty")
    v3.push_back("forty")
    v3.push_back("fifty")
    v3.push_back("sixty")
    v3.push_back("seventy")
    v3.push_back("eighty")
    v3.push_back("ninety")

fn string_length(n: Int) -> Int:
    if n == 0:
        return 0
    elif n <= 10:
        return len(v1[n-1])
    elif n < 20:
        return len(v2[n-11])
    elif n < 100:
        let q = n // 10
        let r = n % 10
        return len(v3[q-2]) + string_length(r)
    elif n < 1000:
        let q = n // 100
        let r = n % 100
        let s100 = string_length(q) + len("hundred")
        if r == 0:
            return s100
        else:
            return s100 + len("and") + string_length(r)
    elif n < 10000:
        let q = n // 1000
        let r = n % 1000
        return string_length(q) + len("thousand") + string_length(r)
    else:
        return 0

fn f(N: Int) -> Int:
    var s = 0
    for n in range(1, N+1):
        s += string_length(n)
    return s

fn main() raises:
    push_to_v1()
    push_to_v2()
    push_to_v3()
    let args = sys.argv()
    let N = atol(args[1])
    print(f(N))

AtCoder Beginner Contest 341 D

https://atcoder.jp/contests/abc341/tasks/abc341_d

包除原理+二分探索です。(first, last]とするとよいです。

// Only one of two
#![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 gcd(n: u64, m: u64) -> u64 {
    if m == 0 {
        n
    }
    else {
        gcd(m, n % m)
    }
}

fn lcm(n: u64, m: u64) -> u64 {
    n / gcd(n, m) * m
}


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

fn read_input() -> (u64, u64, u64) {
    let v = read_vec();
    let (N, M, K) = (v[0], v[1], v[2]);
    (N, M, K)
}

// (first, last]
fn bin_search(first: u64, last: u64, N: u64, M: u64, K: u64) -> u64 {
    let L = lcm(N, M);
    let f = |x| {
        x / N + x / M - x / L * 2
    };
    
    let mid = (first + last) / 2;
    if last - first == 1 {
        last
    }
    else if f(mid) >= K {
        bin_search(first, mid, N, M, K)
    }
    else {
        bin_search(mid, last, N, M, K)
    }
}

fn F(N: u64, M: u64, K: u64) -> u64 {
    bin_search(K-1, K*(N+M), N, M, K)
}

fn main() {
    let (N, M, K) = read_input();
    println!("{}", F(N, M, K))
}

MojoでProject Euler 16

https://projecteuler.net/problem=16

Problem 13のBigIntegerに掛け算を付け加えただけです。

from math import max
import sys


#################### BigInteger ####################

struct BigInteger(CollectionElement):
    var v: DynamicVector[Int]
    
    fn __init__(inout self, v: DynamicVector[Int]):
        self.v = v
    
    fn __copyinit__(inout self, other: BigInteger):
        self.v = other.v
    
    fn __moveinit__(inout self, owned other: BigInteger):
        self.v = other.v^
    
    fn __add__(self, other: BigInteger) -> BigInteger:
        var v = DynamicVector[Int]()
        var carry = 0
        for i in range(max(self.v.size, other.v.size)):
            let d1 = self.v[i] if i < self.v.size else 0
            let d2 = other.v[i] if i < other.v.size else 0
            let n = d1 + d2 + carry
            let d = n % 10
            v.push_back(d)
            carry = n // 10
        if carry > 0:
            v.push_back(carry)
        return BigInteger(v)
    
    fn __mul__(self, other: Int) -> BigInteger:
        var v = DynamicVector[Int]()
        var carry = 0
        for i in range(self.v.size):
            let n = self.v[i] * 2 + carry
            let d = n % 10
            v.push_back(d)
            carry = n // 10
        if carry > 0:
            v.push_back(carry)
        return BigInteger(v)
    
    fn __str__(self) -> String:
        var s: String = ""
        for i in range(self.v.size-1, -1, -1):
            s += String(self.v[i])
        return s
    
    @staticmethod
    fn create(n: Int) -> BigInteger:
        var v = DynamicVector[Int]()
        v.push_back(n)
        return BigInteger(v)
    
    @staticmethod
    fn parse(s: String) -> BigInteger:
        var v = DynamicVector[Int]()
        for i in range(len(s)-1, -1, -1):
            v.push_back(ord(s[i]) - 48)
        return BigInteger(v)


#################### process ####################

fn sum(v: DynamicVector[Int]) -> Int:
    var s: Int = 0
    for i in range(v.size):
        s += v[i]
    return s

fn f(N: Int) -> Int:
    var n = BigInteger.create(1)
    for i in range(N):
        n = n * 2
    return sum(n.v)

fn main() raises:
    let args = sys.argv()
    let N = atol(args[1])
    print(f(N))

AtCoder Beginner Contest 340 F

https://atcoder.jp/contests/abc340/tasks/abc340_f

 |AY - BX| = 2を解くだけですが、けっこういやらしいですね。

// F - S = 1
#![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()
}

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


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

fn read_input() -> (i64, i64) {
    let v: Vec<i64> = read_vec();
    let (X, Y) = (v[0], v[1]);
    (X, Y)
}

fn shift_core(a: i64, b: i64, X: i64, Y: i64) -> (i64, i64) {
    let mut min_e = min(a.abs(), b.abs());
    let (mut a1, mut b1) = (a, b);
    loop {
        a1 += X;
        b1 += Y;
        if min(a1.abs(), b1.abs()) >= min_e {
            a1 -= X;
            b1 -= Y;
            break
        }
        min_e = min(a1.abs(), b1.abs());
    }
    let (mut a2, mut b2) = (a, b);
    loop {
        a2 -= X;
        b2 -= Y;
        if min(a2.abs(), b2.abs()) >= min_e {
            break
        }
        min_e = min(a2.abs(), b2.abs());
        a1 = a2;
        b1 = b2
    }
    (a1, b1)
}

const D: i64 = 10_i64.pow(18);

fn select((A1, B1): (i64, i64), (A2, B2): (i64, i64)) -> Option<(i64, i64)> {
    let min1 = min(A1.abs(), B1.abs());
    let min2 = min(A2.abs(), B2.abs());
    if min1 > D {
        if min2 > D {
            None
        }
        else {
            Some((A2, B2))
        }
    }
    else {
        if min1 < min2 {
            Some((A1, B1))
        }
        else {
            Some((A2, B2))
        }
    }
}

fn XOR(b1: bool, b2: bool) -> bool {
    b1 != b2
}

fn shift(a: i64, b: i64, X: i64, Y: i64) -> Option<(i64, i64)> {
    if XOR(X > 0, Y > 0) {  // different sign
        select(shift_core(a, -b, X, Y), shift_core(-a, b, X, Y))
    }
    else {
        select(shift_core(a, b, X, Y), shift_core(-a, -b, X, Y))
    }
}

fn F_core(X: i64, Y: i64) -> Option<(i64, i64)> {
    if Y == 0 {
        if X.abs() <= 2 {
            return Some((0, 2 / X))
        }
        else {
            return None
        }
    }
    else if X == 0 {
        if Y.abs() <= 2 {
            return Some((2 / Y, 0))
        }
        else {
            return None
        }
    }
    else if X % 2 == 0 && Y % 2 == 0 {
        let (a, b) = linear_diophantine(Y.abs()/2, X.abs()/2)?;
        shift(a, b, X, Y)
    }
    else {
        let (a, b) = linear_diophantine(Y.abs(), X.abs())?;
        shift(a*2, b*2, X, Y)
    }
}

fn F(X: i64, Y: i64) {
    if let Some((A, B)) = F_core(X, Y) {
        println!("{} {}", A, B)
    }
    else {
        println!("-1")
    }
}

fn main() {
    let (X, Y) = read_input();
    F(X, Y)
}