AtCoder Beginner Contest 345 D

https://atcoder.jp/contests/abc345/tasks/abc345_d

しらみつぶしで十分間に合います。次に長方形を置く場所を決めるとき、必ず左上から左に空いているマスを探します。

// Tiling
#![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" } else { "No" }.to_string()
}


//////////////////// Table ////////////////////

type Rectangle = (usize, usize);
type Position = (usize, usize);

fn read_rect() -> Rectangle {
    let v = read_vec();
    let (A, B) = (v[0], v[1]);
    (A, B)
}

fn rotate(rect: &Rectangle) -> Rectangle {
    (rect.1, rect.0)
}

struct Table {
    table: Vec<Vec<bool>>
}

impl Table {
    fn new(H: usize, W: usize) -> Table {
        let table = vec![vec![false; W]; H];
        Table { table }
    }
    
    fn is_filled(&self) -> bool {
        for v in self.table.iter() {
            for b in v.iter() {
                if !b {
                    return false
                }
            }
        }
        true
    }
    
    fn start_position(&self) -> Position {
        for (i, v) in self.table.iter().enumerate() {
            for (j, b) in v.iter().enumerate() {
                if !b {
                    return (i, j)
                }
            }
        }
        (0, 0)  // dummy
    }
    
    fn is_placable(&self, rect: &Rectangle, pos: Position) -> bool {
        if rect.0 + pos.0 > self.table.len() ||
                    rect.1 + pos.1 > self.table[0].len() {
            return false
        }
        
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                if self.table[i+pos.0][j+pos.1] {
                    return false
                }
            }
        }
        true
    }
    
    fn place(&mut self, rect: &Rectangle, pos: Position) {
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                self.table[i+pos.0][j+pos.1] = true
            }
        }
    }
    
    fn remove(&mut self, rect: &Rectangle, pos: Position) {
        for i in 0..rect.0 {
            for j in 0..rect.1 {
                self.table[i+pos.0][j+pos.1] = false
            }
        }
    }
}


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

fn read_input() -> (usize, usize, Vec<Rectangle>) {
    let v = read_vec();
    let (N, H, W) = (v[0], v[1], v[2]);
    let rects: Vec<Rectangle> = (0..N).map(|_| read_rect()).collect();
    (H, W, rects)
}

fn F_core(rects: &Vec<Rectangle>, table: &mut Table) -> bool {
    if table.is_filled() {
        return true
    }
    
    let pos = table.start_position();
    for (i, rect) in rects.iter().enumerate() {
        let new_rects = rects.iter().enumerate().filter(|&(j, _)| j != i).
                                        map(|(_, &r)| r).collect::<Vec<_>>();
        if table.is_placable(rect, pos) {
            table.place(rect, pos);
            if F_core(&new_rects, table) {
                return true
            }
            else {
                table.remove(rect, pos)
            }
        }
        let rot_rect = rotate(rect);
        if table.is_placable(&rot_rect, pos) {
            table.place(&rot_rect, pos);
            if F_core(&new_rects, table) {
                return true
            }
            else {
                table.remove(&rot_rect, pos)
            }
        }
    }
    false
}

fn F(H: usize, W: usize, rects: Vec<Rectangle>) -> bool {
    let mut table = Table::new(H, W);
    F_core(&rects, &mut table)
}

fn main() {
    let (H, W, rects) = read_input();
    println!("{}", YesNo(F(H, W, rects)))
}

MojoでProject Euler 23

https://projecteuler.net/problem=23

素直に23111までの過剰数を求めて総当たりします。

import sys


#################### library ####################

def div_pow(n: Int, d: Int) -> Tuple[Int, Int]:
    var m = n
    var e = 0
    while m % d == 0:
        e += 1
        m //= d
    return (e, m)


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

def make_sum_divisors_table(N: Int) -> DynamicVector[Int]:
    var a = DynamicVector[Int]()
    var b = DynamicVector[Int]()
    for i in range(N):
        a.push_back(i)
        b.push_back(1)
    
    for p in range(2, N):
        if p*p > N:
            break
        if a[p] == 1:
            continue
        for n in range(p, N, p):
            m = 1
            while a[n] % p == 0:
                m = m * p + 1
                a[n] /= p
            b[n] *= m
    
    for n in range(2, N):
        if a[n] != 1:
            b[n] *= a[n] + 1
    return b

fn is_enough_each(r: Int, table: DynamicVector[Int]) -> Bool:
    for i in range(r, table.size, 6):
        if table[i] > i * 2:
            return True
    return False

fn make_abundant_list(M: Int) -> DynamicVector[Int]:
    var ns = DynamicVector[Int]()
    try:
        var table = make_sum_divisors_table(M)
        for n in range(12, M):
            if table[n] > n * 2:
                ns.push_back(n)
    except:
        pass
    return ns

fn f() raises -> Int:
    var N = 28123
    var ab_list = make_abundant_list(N-12)
    var bs = DynamicVector[Bool]()
    for _ in range(N+1):
        bs.push_back(False)
    
    for i in range(ab_list.size):
        var ab1 = ab_list[i]
        for j in range(i, ab_list.size):
            var ab2 = ab_list[j]
            var n = ab1 + ab2
            if n > N:
                break
            bs[n] = True
    
    var s = 0
    for n in range(1, N+1):
        if not bs[n]:
            s += n
    return s

fn main() raises:
    print(f())

MojoでProject Euler 22

https://projecteuler.net/problem=22

ファイルを読むのもまだめんどうなようです。1行ずつ読むメソッドも無いようです。今回の問題は最初から1行ですが。
DynamicVector[Int]はソートする関数が用意されているようですが、DynamicVector[String]は無いようです。仕方ないので実装しました。文字列の比較もできないので、それも実装しました。

from math import min
from random import random_ui64

fn less_than(s1: String, s2: String) -> Bool:
    for i in range(min(len(s1), len(s2))):
        if ord(s1[i]) != ord(s2[i]):
            return ord(s1[i]) < ord(s2[i])
    return len(s1) < len(s2)

fn sort(v: DynamicVector[String]) -> DynamicVector[String]:
    if v.size <= 1:
        return v
    else:
        var pivot_index = int(random_ui64(0, v.size-1))
        var pivot = v[pivot_index]
        var v1 = DynamicVector[String]()
        var v2 = DynamicVector[String]()
        for i in range(v.size):
            if i == pivot_index:
                pass
            elif less_than(v[i], pivot):
                v1.push_back(v[i])
            else:
                v2.push_back(v[i])
        
        var w1 = sort(v1)
        var w2 = sort(v2)
        w1.push_back(pivot)
        for s in w2:
            w1.push_back(s[])
        return w1

fn arrange(data: String) -> DynamicVector[String]:
    try:
        var v = data.split("\"")
        var w = DynamicVector[String]()
        for i in range(1, v.size, 2):
            w.push_back(v[i])
        return sort(w)
    except:
        return DynamicVector[String]()

fn score(s: String) -> Int:
    var sc = 0
    for c in s.as_bytes():
        sc += int(c[] - ord("A") + 1)
    return sc

fn sum_scores(data: String) -> Int:
    var v = arrange(data)
    var s = 0
    for i in range(v.size):
        s += (i + 1) * score(v[i])
    return s

fn f(path: String) -> Int:
    try:
        with open(path, "r") as f:
            var data = f.read()
            return sum_scores(data)
    except:
        return 0

fn main():
    print(f("0022_names.txt"))

MojoでProject Euler 21

https://projecteuler.net/problem=21

約数の和はエラトステネスのふるいのようにまとめて求められますが、元々の値をオーバーしたら個別に素因数分解して求めます。

import sys


#################### library ####################

def div_pow(n: Int, d: Int) -> Tuple[Int, Int]:
    var m = n
    var e = 0
    while m % d == 0:
        e += 1
        m //= d
    return (e, m)


#################### Factors ####################

struct Factors(CollectionElement):
    var fs: DynamicVector[Tuple[Int, Int]]
    
    fn __init__(inout self, fs: DynamicVector[Tuple[Int, Int]]):
        self.fs = fs
    
    fn __copyinit__(inout self, other: Factors):
        self.fs = other.fs
    
    fn __moveinit__(inout self, owned other: Factors):
        self.fs = other.fs^
    
    fn sum_divisors(self) -> Int:
        var m = 1
        for a in self.fs:
            var p = a[].get[0, Int]()
            var e = a[].get[1, Int]()
            var m1 = 1
            for _ in range(e):
                m1 = m1 * p + 1
            m *= m1
        return m
    
    @staticmethod
    fn create(n: Int) raises -> Factors:
        var fs = DynamicVector[Tuple[Int, Int]]()
        var m = n
        for p in range(2, n+1):
            if p*p > m:
                break
            elif m%p == 0:
                var a = div_pow(m, p)
                var e = a.get[0, Int]()
                fs.push_back((p, e))
                m = a.get[1, Int]()
        if m > 1:
            fs.push_back((m, 1))
        return Factors(fs)


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

def make_sum_divisors_table(N: Int) -> DynamicVector[Int]:
    var a = DynamicVector[Int]()
    var b = DynamicVector[Int]()
    for i in range(N):
        a.push_back(i)
        b.push_back(1)
    
    for p in range(2, N):
        if p*p > N:
            break
        if a[p] == 1:
            continue
        for n in range(p, N, p):
            m = 1
            while a[n] % p == 0:
                m = m * p + 1
                a[n] /= p
            b[n] *= m
    
    for n in range(2, N):
        if a[n] != 1:
            b[n] *= a[n] + 1
    return b

fn f(N: Int) raises -> Int:
    var s = 0
    var table = make_sum_divisors_table(N)
    for n in range(2, N):
        var m = table[n] - n
        var s1 = table[m] if m < N else Factors.create(m).sum_divisors()
        if n == s1 - m and n != m:
            s += n
    return s

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

AtCoder Beginner Contest 344 E

https://atcoder.jp/contests/abc344/tasks/abc344_e

双方向リストを作って、それぞれのノードの値とノード自体を辞書にすればいいのですが、ノードをいくつも共有しなければならないので、たぶん参照カウントを使うしかないです。そうすると非常に複雑になって、AIが無いと厳しいですね。

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


//////////////////// Node ////////////////////

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

type Link = Option<Rc<RefCell<Node>>>;

struct Node {
    value: i32,
    prev: Link,
    next: Link,
}

impl Node {
    fn new(v: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            value: v,
            prev: None,
            next: None,
        }))
    }
}

struct BidirectionalList {
    top: Link,
    dic: HashMap<i32, Link>,
}

impl BidirectionalList {
    fn new(top: Link, dic: HashMap<i32, Link>) -> BidirectionalList {
        BidirectionalList { top, dic }
    }
    
    fn insert(&mut self, x: i32, y: i32) {
        let node = self.dic.get(&x).unwrap().clone();
        let new_node = Node::new(y);
        self.dic.insert(y, Some(Rc::clone(&new_node)));
        new_node.borrow_mut().prev = node.clone();
        let next_node = node.as_ref().unwrap().borrow().next.clone();
        node.as_ref().unwrap().borrow_mut().next = Some(new_node.clone());
        if let Some(next_node) = next_node {
            new_node.borrow_mut().next = Some(next_node.clone());
            next_node.borrow_mut().prev = Some(new_node);
        }
    }
    
    fn remove(&mut self, x: i32) {
        let node_ = self.dic.remove(&x).unwrap();
        let node = node_.as_ref().unwrap();
        let prev_node = node.borrow().prev.clone();
        let next_node = node.borrow().next.clone();
        if let Some(ref prev_node) = prev_node {
            prev_node.borrow_mut().next = next_node.clone();
        } else if let Some(ref next_node) = next_node {
            self.top = Some(next_node.clone());
        }
        if let Some(next_node) = next_node {
            next_node.borrow_mut().prev = prev_node;
        }
    }
    
    fn to_vec(&self) -> Vec<i32> {
        let mut vs = vec![];
        let mut v = self.top.clone();
        while let Some(node) = v {
            vs.push(node.borrow().value);
            v = node.borrow().next.clone();
        }
        vs
    }
    
    fn create(A: Vec<i32>) -> BidirectionalList {
        let N = A.len();
        let nodes: Vec<Link> = A.into_iter().
                                map(|e| Some(Node::new(e))).collect();
        for i in 0..N {
            let mut node = nodes[i].as_ref().unwrap().borrow_mut();
            node.prev = if i == 0 { None } else { nodes[i-1].clone() };
            node.next = if i == N - 1 { None } else { nodes[i+1].clone() };
        }
        let dic: HashMap<i32, Link> = nodes.iter().
                map(|node| (node.as_ref().unwrap().borrow().value,
                                                    node.clone())).collect();
        BidirectionalList::new(nodes[0].clone(), dic)
    }
}


//////////////////// Query ////////////////////

enum Query {
    Insert(i32, i32),
    Remove(i32),
}

impl Query {
    fn read() -> Query {
        let v: Vec<i32> = read_vec();
        if v[0] == 1 {
            Query::Insert(v[1], v[2])
        }
        else {
            Query::Remove(v[1])
        }
    }
}


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

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

fn F(A: Vec<i32>, Q: usize) {
    let mut blist = BidirectionalList::create(A);
    for _ in 0..Q {
        match Query::read() {
            Query::Insert(x, y) => blist.insert(x, y),
            Query::Remove(x)    => blist.remove(x)
        }
    }
    let v = blist.to_vec();
    println!("{}", v.into_iter().map(|e| e.to_string()).
                            collect::<Vec<_>>().join(" "));
}

fn main() {
    let (A, Q) = read_input();
    F(A, Q)
}

AtCoder Beginner Contest 344 D

https://atcoder.jp/contests/abc344/tasks/abc344_d

単なるDPですね。どこまで一致したかが状態で、そのなかで最小の金額を記憶しておきます。

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


//////////////////// Bag ////////////////////

type Bag = Vec<String>;

fn read_bag() -> Bag {
    let mut v: Vec<String> = read_vec();
    v.remove(0);
    v
}


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

fn read_input() -> (String, Vec<Bag>) {
    let T: String = read();
    let N: usize = read();
    let bags: Vec<Bag> = (0..N).map(|_| read_bag()).collect();
    (T, bags)
}

fn initialize_dp(L: usize) -> Vec<i32> {
    let mut dp: Vec<i32> = vec![-1; L+1];
    dp[0] = 0;
    dp
}

fn update_dp(bag: Bag, dp: Vec<i32>, T: &String) -> Vec<i32> {
    let mut new_dp: Vec<i32> = dp.to_vec();
    for (i, n) in dp.into_iter().enumerate() {
        if n == -1 {
            continue
        }
        for s in bag.iter() {
            let j = i + s.len();
            if j <= T.len() && s == &T[i..j] {
                if new_dp[j] == -1 {
                    new_dp[j] = n + 1
                }
                else {
                    new_dp[j] = min(new_dp[j], n + 1)
                }
            }
        }
    }
    new_dp
}

fn F(T: String, bags: Vec<Bag>) -> i32 {
    let L = T.len();
    let mut dp = initialize_dp(L);
    for bag in bags.into_iter() {
        dp = update_dp(bag, dp, &T)
    }
    dp[L]
}

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

MojoでProject Euler 20

https://projecteuler.net/problem=20

DynamicVectorに__iter__()が実装されたようです。ただし、所有権は放棄しないので、Reference型を返します。これをデリファレンスするには、

for e in v:
    print(e[])

のようにします。

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)):
            var d1 = self.v[i] if i < self.v.size else 0
            var d2 = other.v[i] if i < other.v.size else 0
            var n = d1 + d2 + carry
            v.push_back(n % 10)
            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 d in self.v:
            var n = d[] * other + carry
            v.push_back(n % 10)
            carry = n // 10
        while carry > 0:
            var r = carry % 10
            carry //= 10
            v.push_back(r)
        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 = 0
    for i in range(v.size):
        s += v[i]
    return s

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

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