AtCoder Beginner Contest 337 E

https://atcoder.jp/contests/abc337/tasks/abc337_e

2進数で考えて、1回ごとに各桁を決めます。すなわち、i桁目が1になるものだけを友人iに

// Bad Juice
#![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 digits(n: usize, b: usize) -> Vec<usize> {
    let mut ds: Vec<usize> = vec![];
    let mut m = n;
    while m > 0 {
        let d = m % b;
        ds.push(d);
        m /= b
    }
    ds
}

fn print_vec(v: Vec<usize>) {
    println!("{}", v.into_iter().map(|n| n.to_string()).
                                    collect::<Vec<String>>().
                                    join(" "))
}

fn output_friend(e: usize, N: usize) {
    let p: usize = 1 << e;
    let mut v: Vec<usize> = vec![];
    for j in (p..N).step_by(p*2) {
        for k in j..min(N, j+p) {
            v.push(k+1)
        }
    }
    v.insert(0, v.len());
    print_vec(v);
}

fn value(s: String) -> usize {
    let bs: Vec<u8> = s.chars().map(|c| (c as u8) - ('0' as u8)).collect();
    bs.into_iter().rev().fold(0, |x, y| x*2 + (y as usize)) + 1
}

fn F(N: usize) -> usize {
    let ds = digits(N-1, 2);
    let M = ds.len();
    println!("{}", M);
    for e in 0..ds.len() {
        output_friend(e, N);
    }
    
    let s: String = read();
    value(s)
}

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

AtCoder Beginner Contest 337 D

https://atcoder.jp/contests/abc337/tasks/abc337_d

1行ごとにDPで最小値を求めます。

// Cheating Gomoku Narabe
#![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 ////////////////////

type Table = Vec<Vec<char>>;

fn read_input() -> (usize, Vec<String>) {
    let v: Vec<usize> = read_vec();
    let (H, K) = (v[0], v[2]);
    let S: Vec<String> = (0..H).map(|_| read::<String>()).collect();
    (K, S)
}

fn transpose(table: &Table) -> Table {
    let H = table.len();
    let W = table[0].len();
    (0..W).map(|j| (0..H).map(|i| table[i][j]).collect::<Vec<char>>()).
                                                        collect::<Table>()
}

fn get_min_plays(num_x: usize, num_o: usize, K: usize) -> usize {
    if num_x == 0 { K - num_o } else { K + 1 }
}

fn find_min_plays_each(v: &Vec<char>, K: usize) -> usize {
    let mut num_x = (0..K).filter(|&j| v[j] == 'x').count();
    let mut num_o = (0..K).filter(|&j| v[j] == 'o').count();
    let mut min_plays = get_min_plays(num_x, num_o, K);
    for j in K..v.len() {
        match v[j-K] {
            'x' => num_x -= 1,
            'o' => num_o -= 1,
            _   => ()
        }
        match v[j] {
            'x' => num_x += 1,
            'o' => num_o += 1,
            _   => ()
        }
        min_plays = min(min_plays, get_min_plays(num_x, num_o, K))
    }
    min_plays
}

fn find_min_plays(table: &Table, K: usize) -> usize {
    if table[0].len() < K {
        return K + 1
    }
    
    let mut min_plays = K + 1;
    for v in table.iter() {
        min_plays = min(min_plays, find_min_plays_each(v, K))
    }
    min_plays
}

fn F(K: usize, S: Vec<String>) -> i32 {
    let table: Table = S.into_iter().
                    map(|s| s.chars().collect::<Vec<char>>()).collect();
    let min_plays1 = find_min_plays(&table, K);
    let table_t = transpose(&table);
    let min_plays2 = find_min_plays(&table_t, K);
    let min_plays = min(min_plays1, min_plays2);
    if min_plays == K + 1 { -1 } else { min_plays as i32 }
}

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

競プロ典型 020

https://atcoder.jp/contests/typical90/tasks/typical90_t

か調べればよいですが、cのべき乗を次々と計算していけばよいです。

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


//////////////////// 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, c: u64) -> bool {
    // log2a < blog2c
    // a < c^b
    let mut p: u64 = 1;
    for _ in 0..b {
        if a / c < p {
            return true
        }
        p *= c
    }
    false
}

fn main() {
    let (a, b, c) = read_input();
    println!("{}", YesNo(F(a, b, c)))
}

MojoでProject Euler 14

https://projecteuler.net/problem=14

メモ化をすれば簡単ですが、グローバルにDynamicVectorを持てますね。

import sys


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

var memo = DynamicVector[Int]()
fn Collatz_length(n: Int) -> Int:
    if n < memo.size and memo[n] != 0:
        return memo[n]
    else:
        let l = Collatz_length(n//2 if n % 2 == 0 else n*3+1) + 1
        if n < memo.size:
            memo[n] = l
        return l

fn f(N: Int) -> Int:
    memo.resize(N, 0)
    memo[1] = 1
    for n in range(2, N):
        memo[n] = Collatz_length(n)
    
    var max_item = (1, 1)
    for n in range(2, N):
        if memo[n] > max_item.get[0, Int]():
            max_item = (memo[n], n)
    return max_item.get[1, Int]()

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

競プロ典型 019

https://atcoder.jp/contests/typical90/tasks/typical90_s

DPで区間を状態にして、単に2つを足すか、両端の差とその間の区間、と考えれば簡単にDPの式が得られます。なぜこの2つかと言うと、両端が残るまで取りつくさないと、どこかで2つに分割するのと同じになるからです。

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


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

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

fn F(A: Vec<i32>) -> i32 {
    let L = A.len();
    let mut dp: Vec<Vec<i32>> = vec![vec![0; L+1]; L];
    for w in (2..L+1).step_by(2) {
        for i in 0..L-w+1 {
            let j = i + w;
            dp[i][j] = (A[i] - A[j-1]).abs() + dp[i+1][j-1];
            for k in (i+2..j-1).step_by(2) {
                let s = dp[i][k] + dp[k][j];
                if s < dp[i][j] {
                    dp[i][j] = s
                }
            }
        }
    }
    dp[0][L]
}

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

AtCoder Beginner Contest 336 E

https://atcoder.jp/contests/abc336/tasks/abc336_e

ある桁和を考えて、上の桁から、数字の和と剰余を状態としたDPを考えればよいです。上限があるのでちょっと嫌らしいです。

// Digit Sum Divisible
#![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 digits(N: i64) -> Vec<i64> {
    let mut ds: Vec<i64> = vec![];
    let mut n = N;
    while n != 0 {
        let d = n % 10;
        ds.push(d);
        n /= 10
    }
    ds
}


//////////////////// DP ////////////////////

use std::collections::HashMap;
type Map = HashMap<(i64, i64), i64>;

struct DP {
    dp1: Map,
    dp2: Map,
    d: i64
}

impl DP {
    fn update(&self, d1: i64) -> DP {
        let mut dp1: Map = HashMap::new();
        let mut dp2: Map = HashMap::new();
        self.update_core(d1, d1 + 1, &self.dp1, &mut dp1);
        self.update_core(0, d1, &self.dp1, &mut dp2);
        self.update_core(0, 10, &self.dp2, &mut dp2);
        DP { dp1, dp2, d: self.d }
    }
    
    fn update_core(&self, first: i64, last: i64,
                                dp_in: &Map, dp_out: &mut Map) {
        for (&(s, r), &n) in dp_in.iter() {
            for d in first..last {
                let key = (s + d, (r * 10 + d) % self.d);
                let e = dp_out.entry(key).or_insert(0);
                *e += n
            }
        }
    }
    
    fn count_core(&self, dp: &Map) -> i64 {
        let mut counter: i64 = 0;
        for (&(s, r), &n) in dp.iter() {
            if s == self.d && r == 0 {
                counter += n
            }
        }
        counter
    }
    
    fn count(&self) -> i64 {
        self.count_core(&self.dp1) + self.count_core(&self.dp2)
    }
    
    fn new(d: i64) -> DP {
        let mut dp1: Map = HashMap::new();
        dp1.insert((0, 0), 1);
        let dp2: Map = HashMap::new();
        DP { dp1, dp2, d }
    }
}


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

fn count_each(d: i64, ds: &Vec<i64>) -> i64 {
    let mut dp = DP::new(d);
    for &d1 in ds.iter().rev() {
        dp = dp.update(d1)
    }
    dp.count()
}

fn F(N: i64) -> i64 {
    let ds = digits(N);
    let max_sum = ds[ds.len()-1] + (ds.len() as i64 - 1) * 9;
    let mut counter: i64 = 0;
    for d in 1..max_sum+1 {
        counter += count_each(d, &ds)
    }
    counter
}

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

AtCoder Beginner Contest 336 D

https://atcoder.jp/contests/abc336/tasks/abc336_d

左から見て、その位置からどこまでがピークになり得るかを調べます。右からも同様です。
入力例1だとそれぞれ0-basedで、

2 2 2 3 4
0 0 1 2 4

そして、上の左から見ていって、2以下で一番右の場所を探します。そうすると、index: 3が2になります。長さは4ですが、ピラミッドは奇数なので長さ3で、サイズは2です。つまり、ある数以下で最も右の位置を探せばよいです。

// Pyramid
#![allow(non_snake_case)]

use std::cmp::{min, 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 ////////////////////

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(B: Vec<usize>) -> SegmentTree {
        let m = B.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<usize> = vec![B.len(); n*2-1];
        for i in n-1..n-1+m {
            v[i] = B[i+1-n]
        }
        for i in (0..n-1).rev() {
            v[i] = min(v[i*2+1], v[i*2+2])
        }
        SegmentTree { n, v }
    }
    
    fn rightmost_le_pos(&self, m: usize) -> usize {
        self.rightmost_le_pos_core(m, 0)
    }
    
    fn rightmost_le_pos_core(&self, m: usize, i: usize) -> usize {
        if i >= self.n - 1 {
            i + 1 - self.n
        }
        else {
            if self.v[i*2+2] <= m {
                self.rightmost_le_pos_core(m, i*2+2)
            }
            else {
                self.rightmost_le_pos_core(m, i*2+1)
            }
        }
    }
}


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

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

fn find_right_limit(A: &Vec<usize>) -> Vec<usize> {
    let N = A.len();
    let mut L: Vec<usize> = vec![N-1; N];
    let mut j: usize = 0;
    for i in 0..N-1 {
        while j < N && 1 + j <= A[j] + i {
            j += 1
        }
        L[i] = j - 1
    }
    L
}

fn find_left_limit(A: &Vec<usize>) -> Vec<usize> {
    let N = A.len();
    let mut L: Vec<usize> = vec![0; N];
    let mut j: usize = N - 1;
    for i in (1..N).rev() {
        while 1 + i <= A[j] + j {
            if j == 0 {
                break
            }
            j -= 1
        }
        L[i] = j + 1
    }
    L
}

fn F(A: Vec<usize>) -> usize {
    let N = A.len();
    let L = find_right_limit(&A);
    let R = find_left_limit(&A);
    
    let tree = SegmentTree::create(R);
    let mut max_size = 0;
    for i in 0..N {
        let j = tree.rightmost_le_pos(L[i]);
        max_size = max(max_size, (j - i + 2) / 2)
    }
    max_size
}

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