3つの正方形は、6通りの配置があって、2つの座標を定めればある長方形の範囲最大の和になります。
Rustなのに時間的にかなり際どいです。木を辿らずにいきなり値を取れるところは取るようにして、やっと通りました。

// Set Add Query
#![allow(non_snake_case)]

use std::cmp::max;


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


//////////////////// Segment Tree ////////////////////

type Val = i64;
type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    m: usize,
    v: Vec<Val>,
}

impl SegmentTree {
    fn max(&self, rng: Range) -> Val {
        if rng == (0, self.m) {
            self.v[0]
        }
        else if rng.0 == rng.1 - 1 {
            self.v[rng.0+self.n-1]
        }
        else {
            self.max_core(rng, 0, self.n, 0)
        }
    }
    
    fn max_core(&self, rng: Range, first: usize, last: usize, i: usize) -> Val {
        if rng.0 <= first && last <= rng.1 {
            self.v[i]
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.max_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.max_core(rng, mid, last, i*2+2)
            }
            else {
                max(self.max_core(rng, first, mid, i*2+1),
                    self.max_core(rng, mid, last, i*2+2))
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(a: &Vec<Val>) -> SegmentTree {
        let m = a.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<Val> = vec![0; n*2-1];
        for i in n-1..n+m-1 {
            v[i] = a[i+1-n]
        }
        for i in (0..n-1).rev() {
            v[i] = max(v[i*2+1], v[i*2+2])
        }
        SegmentTree { n, m, v }
    }
    
    fn max_segment(s1: &SegmentTree, s2: &SegmentTree) -> SegmentTree {
        let v: Vec<Val> = s1.v.iter().zip(s2.v.iter()).
                                map(|(&a, &b)| max(a, b)).collect();
        SegmentTree { n: s1.n, m: s1.m, v }
    }
}


//////////////////// Segment Tree 2D ////////////////////

struct SegmentTree2D {
    n: usize,
    m: usize,
    v: Vec<SegmentTree>,
}

impl SegmentTree2D {
    fn max(&self, rng1: Range, rng2: Range) -> Val {
        if rng1 == (0, self.m) {
            self.v[0].max(rng2)
        }
        else if rng1.0 == rng1.1 - 1 {
            self.v[rng1.0+self.n-1].max(rng2)
        }
        else {
            self.max_core(rng1, rng2, 0, self.n, 0)
        }
    }
    
    fn max_core(&self, rng1: Range, rng2: Range,
                        first: usize, last: usize, i: usize) -> Val {
        if rng1.0 <= first && last <= rng1.1 {
            self.v[i].max(rng2)
        }
        else {
            let mid = (first + last) / 2;
            if rng1.1 <= mid {
                self.max_core(rng1, rng2, first, mid, i*2+1)
            }
            else if rng1.0 >= mid {
                self.max_core(rng1, rng2, mid, last, i*2+2)
            }
            else {
                max(self.max_core(rng1, rng2, first, mid, i*2+1),
                    self.max_core(rng1, rng2, mid, last, i*2+2))
            }
        }
    }
    
    fn row_max(&self, i: usize) -> i64 {
        self.v[i+self.n-1].v[0]
    }
    
    fn column_max(&self, j: usize) -> i64 {
        let tree = &self.v[0];
        tree.v[j+tree.n-1]
    }
    
    fn create(A: &Vec<Vec<Val>>) -> SegmentTree2D {
        let m = A.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<SegmentTree> = vec![];
        for _ in 0..n*2-1 {
            // 仮のSegmentTreeを登録
            let w: Vec<Val> = vec![0];
            v.push(SegmentTree { n: 1, m, v: w })
        }
        for i in n-1..n+m-1 {
            v[i] = SegmentTree::create(&A[i+1-n])
        }
        for i in n+m-1..n*2-1 {
            v[i] = SegmentTree::create(&vec![0; n*2-1])
        }
        for i in (0..n-1).rev() {
            v[i] = SegmentTree::max_segment(&v[i*2+1], &v[i*2+2])
        }
        SegmentTree2D { n, m, v }
    }
}


//////////////////// Matrix ////////////////////

type Matrix = Vec<Vec<i64>>;


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

struct Table {
    N: usize,
    M: usize,
    tree: SegmentTree2D
}

impl Table {
    fn max(&self) -> i64 {
        let v: Vec<i64> = vec![self.max1(), self.max2(), self.max3(),
                               self.max4(), self.max5(), self.max6()];
        v.into_iter().fold(0, |x, y| max(x, y))
    }
    
    // 1 2
    //  3
    fn max1(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in self.M..self.N-self.M+1 {      // 3の縦座標
            for j in 0..self.N-self.M*2+1 {     // 1の横座標
                let max1 = self.tree.max(self.above(i), (j, j+1));
                let max2 = self.tree.max(self.above(i), self.right(j));
                let max3 = self.tree.row_max(i);
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    //  3
    // 1 2
    fn max2(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 3の縦座標
            for j in 0..self.N-self.M*2+1 {     // 1の横座標
                let max1 = self.tree.max(self.below(i), (j, j+1));
                let max2 = self.tree.max(self.below(i), self.right(j));
                let max3 = self.tree.row_max(i);
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    // 1
    //   2
    // 3
    fn max3(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 1の縦座標
            for j in self.M..self.N-self.M+1 {  // 2の横座標
                let max1 = self.tree.max((i, i+1), self.left(j));
                let max2 = self.tree.column_max(j);
                let max3 = self.tree.max(self.below(i), self.left(j));
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    //   1
    // 2
    //   3
    fn max4(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 1の縦座標
            for j in 0..self.N-self.M*2+1 {     // 2の横座標
                let max1 = self.tree.max((i, i+1), self.right(j));
                let max2 = self.tree.column_max(j);
                let max3 = self.tree.max(self.below(i), self.right(j));
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    // 1 2 3
    fn max5(&self) -> i64 {
        let mut max_value: i64 = 0;
        for j in self.M..self.N-self.M*2+1 {    // 真ん中の横座標
            let max1 = self.tree.max((0, self.N-self.M+1), self.left(j));
            let max2 = self.tree.max((0, self.N-self.M+1), (j, j+1));
            let max3 = self.tree.max((0, self.N-self.M+1), self.right(j));
            max_value = max(max_value, max1 + max2 + max3);
        }
        max_value
    }
    
    // 1
    // 2
    // 3
    fn max6(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in self.M..self.N-self.M*2+1 {    // 真ん中の縦座標
            let max1 = self.tree.max(self.above(i), (0, self.N-self.M+1));
            let max2 = self.tree.row_max(i);
            let max3 = self.tree.max(self.below(i), (0, self.N-self.M+1));
            max_value = max(max_value, max1 + max2 + max3);
        }
        max_value
    }
    
    fn above(&self, i: usize) -> Range {
        (0, i-self.M+1)
    }
    
    fn below(&self, i: usize) -> Range {
        (i+self.M, self.N-self.M+1)
    }
    
    fn left(&self, j: usize) -> Range {
        (0, j-self.M+1)
    }
    
    fn right(&self, j: usize) -> Range {
        (j+self.M, self.N-self.M+1)
    }
    
    fn accumulate(A: &Matrix) -> Matrix {
        let N = A.len();
        let mut B: Matrix = vec![vec![0; N+1]; N+1];
        for i in 0..N {
            for j in 0..N {
                B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i][j]
            }
        }
        B
    }
    
    fn make_sum_matrix(M: usize, B: &Matrix) -> Matrix {
        let N = B.len() - 1;
        let L = N - M + 1;
        let mut C: Matrix = vec![vec![0; L]; L];
        for i in 0..L {
            for j in 0..L {
                C[i][j] = B[i+M][j+M] - B[i][j+M] - B[i+M][j] + B[i][j]
            }
        }
        C
    }
}


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

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

fn make_table(M: usize, A: Matrix) -> Table {
    let N = A.len();
    let B = Table::accumulate(&A);
    let C = Table::make_sum_matrix(M, &B);
    let tree = SegmentTree2D::create(&C);
    Table { N, M, tree }
}

fn F(M: usize, A: Matrix) -> i64 {
    let table = make_table(M, A);
    table.max()
}

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

2024-04-02

AtCoder Beginner Contest 347 E

https://atcoder.jp/contests/abc347/tasks/abc347_e

時系列でSの大きさを記録します。実際には累積和をVecにします。

// Set Add Query
#![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()
}

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, Vec<usize>) {
    let v = read_vec();
    let N = v[0];
    let X_: Vec<usize> = read_vec();
    let X: Vec<usize> = X_.into_iter().map(|x| x - 1).collect();
    (N, X)
}

fn F(N: usize, X: Vec<usize>) -> Vec<usize> {
    let mut A: Vec<usize> = vec![0; N];
    let mut acc: Vec<usize> = vec![0];
    let mut dic: HashMap<usize, usize> = HashMap::new();
    for (p, x) in X.into_iter().enumerate() {
        if dic.contains_key(&x) {
            let q = dic.get(&x).unwrap();
            A[x] += acc[p] - acc[*q];
            dic.remove(&x);
        }
        else {
            dic.insert(x, p);
        }
        acc.push(acc.last().unwrap() + dic.len())
    }
    
    for (x, p) in dic.into_iter() {
        A[x] += acc.last().unwrap() - acc[p]
    }
    A
}

fn main() {
    let (N, X) = read_input();
    let A = F(N, X);
    println!("{}", A.into_iter().map(|a| a.to_string()).
                                    collect::<Vec<_>>().join(" "))
}

2024-04-01

AtCoder Beginner Contest 347 D

https://atcoder.jp/contests/abc347/tasks/abc347_d

aとbとpopcount(C)で、Cの1をどちらに何個1にするか、0を何個1にするかが決まります。

// Popcount and XOR
#![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 popcount(n: u64) -> u64 {
    if n == 0 { 0 } else { (n & 1) + popcount(n >> 1) }
}

fn b2d(bs: Vec<u64>) -> u64 {
    let mut d = 0;
    for i in (0..bs.len()).rev() {
        d = d * 2 + bs[i]
    }
    d
}


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

fn read_input() -> (u64, u64, u64) {
    let v = read_vec();
    let (a, b, C) = (v[0], v[1], v[2]);
    (a, b, C)
}

fn F(a: u64, b: u64, mut C: u64) -> Option<(u64, u64)> {
    let p = popcount(C);
    if a + b < p || a + p < b || b + p < a || (a + b) % 2 != p % 2 {
        return None
    }
    
    let mut bs1: Vec<u64> = vec![];
    let mut bs2: Vec<u64> = vec![];
    let mut c1: u64 = 0;
    let mut c3: u64 = 0;
    let c1_max = (a + p - b) / 2;
    let c3_max = a - c1_max;
    while C != 0 {
        let b1 = C & 1;
        C >>= 1;
        if b1 == 1 {
            if c1 < c1_max {
                bs1.push(1);
                bs2.push(0);
                c1 += 1
            }
            else {
                bs1.push(0);
                bs2.push(1);
            }
        }
        else if c3 < c3_max {
            bs1.push(1);
            bs2.push(1);
            c3 += 1
        }
        else {
            bs1.push(0);
            bs2.push(0)
        }
    }
    
    for _ in 0..a-c1-c3 {
        bs1.push(1);
        bs2.push(1)
    }
    
    if bs1.len() > 60 {
        return None
    }
    
    return Some((b2d(bs1), b2d(bs2)))
}

fn main() {
    let (a, b, C) = read_input();
    match F(a, b, C) {
        Some((X, Y)) => println!("{} {}", X, Y),
        None         => println!("-1")
    }
}

2024-03-28

AtCoder Beginner Contest 346 F

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

直接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))

inamori’s diary

AtCoder Beginner Contest 347 F