直接kを求めるのは難しいですが、kを与えて部分列かを調べるのは比較的易しいので、二分探索を行います。

// SSttrriinngg in StringString
#![allow(non_snake_case)]

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


//////////////////// PosDict ////////////////////

type Pos = (usize, usize);

struct PosDict {
    N: usize,
    dic: HashMap<char, Vec<usize>>,
    L: usize,
}

impl PosDict {
    fn create(N: usize, S: String) -> PosDict {
        let mut dic: HashMap<char, Vec<usize>> = HashMap::new();
        for (p, c) in S.chars().enumerate() {
            let e = dic.entry(c).or_insert(vec![]);
            (*e).push(p)
        }
        PosDict { N, dic, L: S.len() }
    }
    
    fn is_subsequence(&self, k: usize, T: &String) -> bool {
        let mut pos = (0, 0);
        for c in T.chars() {
            let res = self.find_last(pos, c, k);
            if res.is_none() {
                return false
            }
            else {
                pos = self.next_pos(res.unwrap())
            }
        }
        true
    }
    
    fn next_pos(&self, pos: Pos) -> Pos {
        if pos.1 < self.L - 1 {
            return (pos.0, pos.1 + 1)
        }
        else {
            return (pos.0 + 1, 0)
        }
    }
    
    fn find_last(&self, pos: Pos, c: char, k: usize) -> Option<Pos> {
        match self.dic.get(&c) {
            None    => None,
            Some(v) => self.find_char_pos(pos, v, k)
        }
    }
    
    fn find_char_pos(&self, pos: Pos, v: &Vec<usize>, k: usize) -> Option<Pos> {
        if pos.0 >= self.N {
            return None
        }
        
        let p1 = pos.1;
        let i1 = self.bin_search(0, v.len()-1, p1, v);
        let k1 = v.len() - i1;
        if k1 >= k {
            return Some((pos.0, v[i1+k-1]))
        }
        
        if v.len() * (self.N - pos.0 - 1) < k - k1 {
            return None
        }
        
        let q = (k + i1 - 1) / v.len();
        let r = (k + i1 - 1) % v.len();
        Some((pos.0 + q, v[r]))
    }
    
    // [first, last]
    fn bin_search(&self, first: usize, last: usize,
                        pos: usize, v: &Vec<usize>) -> usize {
        if pos > v[last] {
            v.len()
        }
        else if last - first < 2 {
            if v[first] < pos {
                last
            }
            else {
                first
            }
        }
        else {
            let mid = (first + last) / 2;
            if v[mid] < pos {
                self.bin_search(mid, last, pos, v)
            }
            else {
                self.bin_search(first, mid, pos, v)
            }
        }
    }
}


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

fn read_input() -> (usize, String, String) {
    let N = read();
    let S = read();
    let T = read();
    (N, S, T)
}

fn bin_search(first: usize, last: usize, T: &String, dic: &PosDict) -> usize {
    if last - first == 1 {
        first
    }
    else {
        let mid = (first + last) / 2;
        if dic.is_subsequence(mid, T) {
            bin_search(mid, last, T, dic)
        }
        else {
            bin_search(first, mid, T, dic)
        }
    }
}

fn F(N: usize, S: String, T: String) -> usize {
    let L = S.len();
    let pos_dic = PosDict::create(N, S);
    bin_search(0, L * N / T.len() + 1, &T, &pos_dic)
}

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

2024-03-25

AtCoder Beginner Contest 346 E

https://atcoder.jp/contests/abc346/tasks/abc346_e

逆から考えればよいです。例1なら、下から見て、1 3 2だから、3行目が2になって、2が4個は確定です。次に、1 3 3ですが、3行目はもう終わったので無視です。2 4 0は、4列目を0にしますが、3行目がすでに確定しているので、2個が0になります。2行目が5になって、4列目は確定しているので、5が3個です。最後に1行目と1、2、3列目が残っているので、3個が0になります。

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


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

type Paint = (i8, usize, usize);

fn read_paint() -> Paint {
    let v = read_vec();
    let T = v[0] as i8;
    let A = v[1];
    let X = v[2];
    (T, A, X)
}

fn read_input() -> (usize, usize, Vec<Paint>) {
    let v = read_vec();
    let (H, W, M) = (v[0], v[1], v[2]);
    let paints: Vec<Paint> = (0..M).map(|_| read_paint()).collect();
    (H, W, paints)
}

fn F(H: usize, W: usize, paints: Vec<Paint>) {
    let max_X = paints.iter().map(|&(_, _, X)| X).max().unwrap();
    let mut counter: Vec<usize> = vec![0; max_X+1];
    let mut set_H: HashSet<usize> = (1..H+1).collect();
    let mut set_W: HashSet<usize> = (1..W+1).collect();
    for (T, A, X) in paints.into_iter().rev() {
        if T == 1 && set_H.contains(&A) {
            counter[X] += set_W.len();
            set_H.remove(&A);
        }
        else if T == 2 && set_W.contains(&A) {
            counter[X] += set_H.len();
            set_W.remove(&A);
        }
    }
    counter[0] += set_H.len() * set_W.len();
    
    let c: Vec<(usize, usize)> = counter.into_iter().enumerate().
                                        filter(|&(_, n)| n != 0).collect();
    println!("{}", c.len());
    for (x, n) in c.into_iter() {
        println!("{} {}", x, n)
    }
}

fn main() {
    let (H, W, paints) = read_input();
    F(H, W, paints)
}

2024-03-24

AtCoder Beginner Contest 346 D

https://atcoder.jp/contests/abc346/tasks/abc346_d

文字列を左から見ていって、位置と直前の文字と隣が同じだったことが何回あるかを状態としてDPします。

// Gomamayo Sequence
#![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() -> (String, Vec<i64>) {
    let _N: usize = read();
    let S: String = read();
    let C: Vec<i64> = read_vec();
    (S, C)
}

type DP = [i64; 4];
const INF: i64 = 1e18 as i64;

fn initialize_dp(d: u8, cost: i64) -> DP {
    if d == 0 {
        [0, cost, INF, INF]
    }
    else {
        [cost, 0, INF, INF]
    }
}

fn update_dp(d: u8, cost: i64, dp: DP) -> DP {
    let mut new_dp: DP = [INF; 4];
    let ud: usize = d as usize;
    for i in 0..4 {
        let prev = i & 1;
        let num_conts = i >> 1;
        for new_ud in 0..2 {
            let num_conts1 = num_conts + if new_ud == prev { 1 } else { 0 };
            if num_conts1 < 2 {
                let new_i = new_ud | (num_conts1 << 1);
                let new_cost = dp[i] + if new_ud == ud { 0 } else { cost };
                new_dp[new_i] = min(new_cost, new_dp[new_i])
            }
        }
    }
    new_dp
}

fn F(S: String, C: Vec<i64>) -> i64 {
    let ds: Vec<u8> = S.chars().map(|c| (c as u8) - 48).collect();
    let mut dp: DP = initialize_dp(ds[0], C[0]);
    for i in 1..ds.len() {
        dp = update_dp(ds[i], C[i], dp)
    }
    min(dp[2], dp[3])
}

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

2024-03-23

MojoでProject Euler 26

https://projecteuler.net/problem=26

各 $n$ に対し、 $10^e \equiv 1 (\mod n)$ となる最小の自然数 $e$ を求めます。オイラーの定理から $10^{\phi(n)} \equiv 1 (\mod n)$ なので、 $\phi(n)$ の約数となります。
実際のところは、素数の大きい方から順に調べて、周期がその数より1小さいものがあれば、その素数が求める答えです。

from math import min
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)

def pow(b: Int, e: Int, d: Int) -> Int:
    if e == 1:
        return b % d
    elif e % 2 == 1:
        return b * pow(b, e-1, d) % d
    else:
        var p = pow(b, e//2, d)
        return p * p % d

fn print_vector(v: DynamicVector[Int]):
    for k in range((v.size + 9) // 10):
        var s = str("")
        for i in range(k*10, min(k*10+10, v.size)):
            s += str(v[i]) + " "
        print(s)


#################### 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 __mul__(self, other: Factors) -> Factors:
        var fs = DynamicVector[Tuple[Int, Int]]()
        var L1 = self.fs.size
        var L2 = other.fs.size
        var k = 0
        var l = 0
        while k < L1 and l < L2:
            var p1 = self.fs[k].get[0, Int]()
            var p2 = other.fs[l].get[0, Int]()
            var e1 = self.fs[k].get[1, Int]()
            var e2 = other.fs[l].get[1, Int]()
            if p1 == p2:
                fs.push_back((p1, e1+e2))
                k += 1
                l += 1
            elif p1 < p2:
                fs.push_back((p1, e1))
                k += 1
            else:
                fs.push_back((p2, e2))
                l += 1
        
        for k1 in range(k, L1):
            fs.push_back(self.fs[k1])
        for l1 in range(l, L2):
            fs.push_back(other.fs[l1])
        return Factors(fs)
    
    @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)


#################### PrimeTable ####################

struct PrimeTable:
    var table: DynamicVector[Int]
    
    fn __init__(inout self, table: DynamicVector[Int]):
        self.table = table
    
    fn factorize(self, n: Int) -> Factors:
        try:
            return Factors(self.factorize_core(n))
        except:
            return Factors(DynamicVector[Tuple[Int, Int]]())
    
    fn factorize_core(self, n: Int) raises -> DynamicVector[Tuple[Int, Int]]:
        if n == 1:
            return DynamicVector[Tuple[Int, Int]]()
        
        var p = self.table[n]
        var a = div_pow(n, p)
        var e = a.get[0, Int]()
        var m = a.get[1, Int]()
        var fs = DynamicVector[Tuple[Int, Int]]()
        fs.push_back((p, e))
        var fs1 = self.factorize_core(m)
        for f in fs1:
            fs.push_back(f[])
        return fs
    
    @staticmethod
    def make_min_prime_table(N: Int) -> PrimeTable:
        var a = DynamicVector[Int]()
        for i in range(N+1):
            a.push_back(1)
        
        for p in range(2, N+1):
            if p*p > N:
                break
            if a[p] != 1:
                continue
            for n in range(p, N+1, p):
                if a[n] == 1:
                    a[n] = p
        
        for n in range(2, N+1):
            if a[n] == 1:
                a[n] = n
        return PrimeTable(a)


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

fn remove25(n: Int) -> Int:
    var m = n
    while m % 2 == 0:
        m //= 2
    while m % 5 == 0:
        m //= 5
    return m

fn phi(fs: Factors) -> Int:
    var m = 1
    for f in fs.fs:
        var p = f[].get[0, Int]()
        var e = f[].get[1, Int]()
        m *= (p-1) * p**(e-1)
    return m

fn period(n: Int, table: PrimeTable) raises -> Int:
    var n1 = remove25(n)
    if n1 == 1:
        return 0
    
    var fs1 = table.factorize(n1)
    var n2 = phi(fs1)
    var fs2 = table.factorize(n2)
    var n3 = n2
    for f2 in fs2.fs:
        var p2 = f2[].get[0, Int]()
        var e2 = f2[].get[1, Int]()
        for e in range(e2-1, -1, -1):
            n3 //= p2
            if pow(10, n3, n1) != 1:
                n3 *= p2
    return n3

fn make_period_table(N: Int) raises -> DynamicVector[Int]:
    var table = PrimeTable.make_min_prime_table(N)
    var periods = DynamicVector[Int]()
    periods.push_back(0)
    periods.push_back(0)
    for n in range(2, N+1):
        periods.push_back(period(n, table))
    return periods

fn max_arg(a: DynamicVector[Int]) -> Int:
    var max_element = a[0]
    var index = 0
    for i in range(1, a.size):
        if a[i] > max_element:
            max_element = a[i]
            index = i
    return index

fn f(N: Int) raises -> Int:
    var periods = make_period_table(N)
    return max_arg(periods)

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

2024-03-22

MojoでProject Euler 25

https://projecteuler.net/problem=25

真面目にフィボナッチ数列を求めてもいいのですが、以下のように概算できます。
漸化式から、

$\displaystyle F_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$
となります。10進でN桁として、
$log_{10}{F_n} \ge N-1$
となる最小の $n$ を求めればよいです。
右辺第2項は小さいので無視すると、
$\displaystyle n \ge \frac{N-1+\log_{10}{5}}{\log_{10}{\frac{1+\sqrt{5}}{2}}}$
となります。
ところで、Mojoにsqrtは無いようなので0.5乗を使います。また数学関数は、SIMD用しか用意されていないので、

    var a = SIMD[DType.float64, 1](2.0)
    var b = log10(a)
    print(b[0])    # 0.3010299956639812

のように、SIMDを経由して計算します。

from math import log10
import sys

fn log10_float(x: Float64) -> Float64:
    var x1 = SIMD[DType.float64, 1](x)
    var y1 = log10(x1)
    return y1[0]

fn f(N: Int) -> Int:
    var beta = (1+5.0**0.5)/2
    var y = log10_float(5.0**0.5)
    return int((N-1+log10_float(5.0**0.5))/log10_float(beta)) + 1

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

2024-03-20

MojoでProject Euler 24

https://projecteuler.net/problem=24

例題で、
["0", "1", "2"]
という配列を用意します。
5番目の順列を決めるのに、
4/2!=2なので、
"2"が頭になります。これを配列から除去して、["0", "1"]となります。
余りが0だったので、0/1!=0で、"0"を取り出します。["1"]となります。
余りが0だったので、0/0!=0で、"1"を取り出します。
合わせて、"201"となります。
DynamicVectorにはPythonのようなpopも無いんですね。

import sys

fn factorial(n: Int) -> Int:
    return 1 if n == 0 else n * factorial(n-1)

fn pop(inout v: DynamicVector[String], i: Int) -> String:
    var w = DynamicVector[String]()
    for j in range(v.size-1, i, -1):
        var e = v.pop_back()
        w.push_back(e)
    var ret = v.pop_back()
    while w.size > 0:
        var e = w.pop_back()
        v.push_back(e)
    return ret

fn g(n: Int, inout ds: DynamicVector[String]) -> String:
    if ds.size == 0:
        return ""
    
    var m = factorial(ds.size-1)
    var q = n // m
    var r = n % m
    var s = pop(ds, q)
    return s + g(r, ds)

fn f(N: Int) -> String:
    var ds = DynamicVector[String]()
    for d in range(10):
        ds.push_back(str(d))
    return g(N-1, ds)

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

2024-03-17

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

inamori’s diary

AtCoder Beginner Contest 346 F