AtCoder Beginner Contest 302 D

https://atcoder.jp/contests/abc302/tasks/abc302_d

Aと同じか小さい一番大きなBを尺取り法で探します。逆もやります。

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

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

fn read_input() -> (i64, Vec<i64>, Vec<i64>) {
    let v = read_vec();
    let D = v[2];
    let A = read_vec();
    let B = read_vec();
    (D, A, B)
}

fn f1(A: &Vec<i64>, B: &Vec<i64>, D: i64) -> i64 {
    let mut k = A.len() - 1;
    let mut l = B.len() - 1;
    while k < A.len() && l < B.len() {
        if A[k] >= B[l] {
            if A[k] - B[l] <= D {
                return A[k] + B[l]
            }
            else {
                k -= 1
            }
        }
        else {
            l -= 1
        }
    }
    -1
}

fn f(D: i64, mut A: Vec<i64>, mut B: Vec<i64>) -> i64 {
    A.sort();
    B.sort();
    max(f1(&A, &B, D), f1(&B, &A, D))
}

//////////////////// main ////////////////////

fn main() {
    let (D, A, B) = read_input();
    println!("{}", f(D, A, B))
}

AtCoder Beginner Contest 301 E

https://atcoder.jp/contests/abc301/tasks/abc301_e

SとGとお菓子マスの距離のグラフにします。そして、グラフをたどっていって、今の位置と今までたどった位置を状態とみなし、その状態の最短距離を求めます。ただ、間に合わないので、各ステップで状態数を距離ソートして10万で打ち切るというインチキをしています。

// Pac-Takahashi
#![allow(non_snake_case)]

use std::collections::{VecDeque, 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 ////////////////////

type Map = Vec<Vec<char>>;
type Node = (usize, usize);

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

fn collect_nodes(A: &Map) -> Vec<Node> {
    let mut nodes: Vec<(usize, usize)> = Vec::new();
    let H = A.len();
    let W = A[0].len();
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'S' {
                nodes.push((i, j))
            }
        }
    }
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'o' {
                nodes.push((i, j))
            }
        }
    }
    for i in 0..W {
        for j in 0..H {
            if A[j][i] == 'G' {
                nodes.push((i, j))
            }
        }
    }
    nodes
}

fn neighbors(node: &Node, A: &Map) -> Vec<Node> {
    let (x, y) = node;
    let H = A.len();
    let W = A[0].len();
    
    let is_inner = |(x, y): &Node| {
        0 < *x && *x <= W && 0 < *y && *y <= H && A[y-1][x-1] != '#'
    };
    
    // 負にならないように1個ずつずらす
    vec![(x+2, y+1), (x+1, y+2), (*x, y+1), (x+1, *y)].into_iter().
                filter(|v| is_inner(v)).
                map(|(x1, y1)| (x1-1, y1-1)).collect::<Vec<Node>>()
}

fn make_distances(node: &Node, nodes: &Vec<Node>, A: &Map) -> Vec<usize> {
    let mut dists: HashMap<Node, usize> = HashMap::new();
    let mut queue = VecDeque::new();
    queue.push_back(*node);
    dists.insert(*node, 0);
    while let Some(v) = queue.pop_front() {
        let neis = neighbors(&v, &A);
        let dist = dists.get(&v).unwrap().clone();
        for w in neis.into_iter() {
            if !dists.contains_key(&w) {
                dists.insert(w, dist + 1);
                queue.push_back(w)
            }
        }
    }
    nodes.iter().map(|v| match dists.get(v) { Some(d) => *d, None => INF }).
                                                        collect::<Vec<usize>>()
}

fn make_distance_table(nodes: &Vec<Node>, A: &Map) -> Vec<Vec<usize>> {
    nodes.iter().map(|v| make_distances(v, nodes, A)).
                                collect::<Vec<Vec<usize>>>()
}

const INF: usize = 10000000;

#[derive(Debug, Eq, PartialEq)]
struct Item {
    dist: usize,
    id: usize,
    flags: i32,
    value: i32
}

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

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

type Dict = HashMap<(usize, i32), usize>;

fn step(dic: Dict, table: &Vec<Vec<usize>>, T: usize) -> Dict {
    let mut new_dic: Dict = HashMap::new();
    for ((i0, flags0), d0) in dic.into_iter() {
        for (i, d) in table[i0].iter().enumerate() {
            if i == i0 || ((flags0 >> i) & 1) == 1 {
                continue
            }
            let dist = d0 + d;
            let flags = flags0 | (1 << i);
            if dist <= T {
                let e = new_dic.entry((i, flags)).or_insert(dist);
                if *e > dist {
                    *e = dist
                }
            }
        }
    }
    new_dic
}

fn f(T: usize, A: Vec<Vec<char>>) -> i32 {
    let nodes = collect_nodes(&A);
    let table = make_distance_table(&nodes, &A);
    let N = table.len();
    let mut max_value: i32 = -1;
    let mut dic: Dict = HashMap::new();     // { (node, flags): dist }
    dic.insert((0, 1), 0);
    for s in 0..N-1 {
        dic = step(dic, &table, T);
        if dic.len() > 100000 {
            let mut a = dic.into_iter().collect::<Vec<((usize, i32), usize)>>();
            a.sort_by_key(|x| x.1);
            dic = a[..100000].into_iter().map(|x| *x).collect::<Dict>()
        }
        if dic.keys().any(|(i, _)| *i == N-1) {
            max_value = s as i32
        }
    }
    max_value
}

//////////////////// main ////////////////////

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

アルゴリズムと数学 057

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aw

これは状態遷移の問題ですね。タイルを左上から並べていきます。すなわち、最もタイルが左にある高さにタイルを敷き詰めます。こう決めることによって、タイルを並べる順番が一意に決まります。
状態を、各高さでタイルがどこまで並んでいるかを状態とします。ただし、一番小さい高さを0に正規化します。具体的にK=3として、最初は[0, 0, 0]で、次に縦と横にタイルを敷けるので、[2, 0, 0]と[1, 1, 0]が考えられます。[2, 0, 0]から縦に敷くと、[2, 1, 1]となりますが、これを正規化して[1, 0, 0]を状態とします。
だから、状態数はけっこう小さいです。なので、どの状態からどの状態へ遷移できるかを行列で表して、行列の(KN/2)乗を計算して、[0, 0, 0]から[0, 0, 0]へのパス数を計算します。より具体的には、[0, 0, 0]を0番として、0番に遷移できればいいので、べき乗した行列をPとすると、P[0][0]がパス数になります。

// Domino Tiling
#![allow(non_snake_case)]

use std::collections::{HashSet, HashMap};


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


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


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

type Matrix = Vec<Vec<i64>>;

fn mat_mul(A: &Matrix, B: &Matrix, d: i64) -> Matrix {
    let L = A.len();
    let M = B.len();
    let N = B[0].len();
    (0..L).map(|i| (0..N).
            map(|j| (0..M).map(|k| (A[i][k] * B[k][j]) % d).sum::<i64>() % d).
                                                    collect::<Vec<i64>>()).
                                                    collect::<Matrix>()
}

fn mat_pow(A: &Matrix, e: u64, d: i64) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 0 {
        let B = mat_pow(&A, e/2, d);
        mat_mul(&B, &B, d)
    }
    else {
        mat_mul(&A, &mat_pow(&A, e-1, d), d)
    }
}


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

type State = Vec<i64>;

fn read_input() -> (usize, usize) {
    let v = read_vec();
    (v[0], v[1])
}

fn normalize(s0: State) -> State {
    let min_x = s0.iter().min().unwrap();
    s0.iter().map(|x| x - min_x).collect::<State>()
}

fn add(s0: &State, y: usize, x: i64) -> State {
    let mut s = s0.clone();
    if x == 1 {
        s[y] += 1;
        s[y+1] += 1
    }
    else {
        s[y] += 2
    }
    normalize(s)
}

fn nexts(s0: &State) -> Vec<State> {
    let H = s0.len();
    let mut states: Vec<State> = Vec::new();
    let y = s0.iter().enumerate().filter(|(_i, &x)| x == 0).
                                    map(|(i, &_x)| i).next().unwrap();
    states.push(add(s0, y, 2));
    if y < H - 1 && s0[y+1] == 0 {
        states.push(add(s0, y, 1))
    }
    states
}

fn state_to_i64(s: &State) -> i64 {
    s.iter().fold(0, |x, y| x * 3 + y)
}

fn collect_edges(K: usize) -> Vec<(i64, i64)> {
    let mut edges: Vec<(i64, i64)> = Vec::new();
    let s0 = vec![0; K];
    let mut stack = vec![s0];
    let mut visited: HashSet<i64> = HashSet::new();
    visited.insert(0);
    while !stack.is_empty() {
        let s = stack.pop().unwrap();
        let neighbors = nexts(&s);
        let hash = state_to_i64(&s);
        for neighbor in neighbors.into_iter() {
            let hash1 = state_to_i64(&neighbor);
            if !visited.contains(&hash1) {
                visited.insert(hash1.clone());
                stack.push(neighbor)
            }
            edges.push((hash, hash1));
        }
    }
    edges
}

fn create_dict(edges: &Vec<(i64, i64)>) -> HashMap<i64, usize> {
    let mut dic: HashMap<i64, usize> = HashMap::new();
    for &(v, w) in edges.iter() {
        if !dic.contains_key(&v) {
            dic.insert(v, dic.len());
        }
        if !dic.contains_key(&w) {
            dic.insert(w, dic.len());
        }
    }
    dic
}

fn make_matrix_core(edges: &Vec<(i64, i64)>, dic: &HashMap<i64, usize>)
                                                            -> Matrix {
    let L = dic.len();
    let mut A: Matrix = (0..L).map(|_| vec![0; L]).collect();
    for &(v, w) in edges.iter() {
        let i = dic[&v];
        let j = dic[&w];
        A[i][j] = 1;
    }
    A
}

fn make_matrix(K: usize) -> Matrix {
    let edges = collect_edges(K);
    let dic = create_dict(&edges);
    make_matrix_core(&edges, &dic)
}

fn f(K: usize, N: usize) -> i64 {
    let A = make_matrix(K);
    let P = mat_pow(&A, (K*N/2) as u64, D);
    P[0][0]
}

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

アルゴリズムと数学 056

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_av

 b_n \equiv a_{n+1}
 c_n \equiv a_{n+2}

とおけば、

 \begin{cases}
a_{n+1} = b_n \\
b_{n+1} = c_n \\
c_{n+1} = a_n + b_n + c_n
\end{cases}

なので、行列表示にすると、

 \begin{pmatrix}
a_{n+1} \\
b_{n+1} \\
c_{n+1}
\end{pmatrix}
= \begin{pmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
a_n \\
b_n \\
c_n
\end{pmatrix}

3×3の行列になるだけで、あとは同じです。

// Recurrence Formula 2
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


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


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

type Matrix = Vec<Vec<i64>>;

fn mat_mul(A: &Matrix, B: &Matrix, d: i64) -> Matrix {
    let L = A.len();
    let M = B.len();
    let N = B[0].len();
    (0..L).map(|i| (0..N).
            map(|j| (0..M).map(|k| (A[i][k] * B[k][j]) % d).sum::<i64>() % d).
                                                    collect::<Vec<i64>>()).
                                                    collect::<Matrix>()
}

fn mat_pow(A: &Matrix, e: u64, d: i64) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 0 {
        let B = mat_pow(&A, e/2, d);
        mat_mul(&B, &B, d)
    }
    else {
        mat_mul(&A, &mat_pow(&A, e-1, d), d)
    }
}


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


fn f(N: u64) -> i64 {
    let A = vec![vec![0, 1, 0], vec![0, 0, 1], vec![1, 1, 1]];
    let P = mat_pow(&A, N-1, D);
    (P[0][0] + P[0][1] + P[0][2] * 2) % D
}

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

アルゴリズムと数学 055

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_au

行列が変わるだけですね。

// Recurrence Formula 1
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 1000000007;


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


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

type Matrix = Vec<Vec<i64>>;

fn mat_mul(A: &Matrix, B: &Matrix, d: i64) -> Matrix {
    let L = A.len();
    let M = B.len();
    let N = B[0].len();
    (0..L).map(|i| (0..N).
            map(|j| (0..M).map(|k| (A[i][k] * B[k][j]) % d).sum::<i64>() % d).
                                                    collect::<Vec<i64>>()).
                                                    collect::<Matrix>()
}

fn mat_pow(A: &Matrix, e: u64, d: i64) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 0 {
        let B = mat_pow(&A, e/2, d);
        mat_mul(&B, &B, d)
    }
    else {
        mat_mul(&A, &mat_pow(&A, e-1, d), d)
    }
}


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


fn f(N: u64) -> i64 {
    let A = vec![vec![0, 1], vec![1, 2]];
    let P = mat_pow(&A, N-2, D);
    (P[1][0] + P[1][1]) % D
}

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

アルゴリズムと数学 054

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_at

 b_n \equiv a_{n+1}とすると、

 \begin{cases}
a_{n+1} = b_n \\
b_{n+1} = a_n + b_n
\end{cases}

と書けます。これを行列表示にすると、

 A \equiv \begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}

とおくと、

 \begin{pmatrix}
a_{n+1} \\
b_{n+1}
\end{pmatrix}
= A
\begin{pmatrix}
a_n \\
b_n
\end{pmatrix}

だから、

 \begin{pmatrix}
a_n \\
b_n
\end{pmatrix}
= A^{n-1}
\begin{pmatrix}
1 \\
1
\end{pmatrix}

となります。あるいは、

 \begin{pmatrix}
a_n \\
b_n
\end{pmatrix}
= A^n
\begin{pmatrix}
0 \\
1
\end{pmatrix}

と書けます。

// Fibonacci Hard (mod 1000000000)
#![allow(non_snake_case)]


//////////////////// Constants ////////////////////

const D: i64 = 1000000000;


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


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

type Matrix = Vec<Vec<i64>>;

fn mat_mul(A: &Matrix, B: &Matrix, d: i64) -> Matrix {
    let L = A.len();
    let M = B.len();
    let N = B[0].len();
    (0..L).map(|i| (0..N).
            map(|j| (0..M).map(|k| (A[i][k] * B[k][j]) % d).sum::<i64>() % d).
                                                    collect::<Vec<i64>>()).
                                                    collect::<Matrix>()
}

fn mat_pow(A: &Matrix, e: u64, d: i64) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 0 {
        let B = mat_pow(&A, e/2, d);
        mat_mul(&B, &B, d)
    }
    else {
        mat_mul(&A, &mat_pow(&A, e-1, d), d)
    }
}


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


fn f(N: u64) -> i64 {
    let A = vec![vec![0, 1], vec![1, 1]];
    let P = mat_pow(&A, N, D);
    P[0][1]
}

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

アルゴリズムと数学 053

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_as

 \displaystyle 4^0 + 4^1 + \cdots 4^N = \frac{4^{N+1} - 1}{3}
を使ってもよいですが、行列などで割り算ができないこともあります。そういう時は繰り返し2乗法のように和を取る方法が使えます。

 1 + a + a^2 + \cdots + a^{2e-1} = (1 + \cdots + a^{e-1}) + a^{e}(1 + \cdots + a^{e-1})

などと再帰的に求めればよいです。

// Sum of 4^N
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: u64 = 1000000007;


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

// n, e, d -> ((1+n+...+n^(e-1)) % d, n^e % d)
fn sum_pow(n: u64, e: u64, d: u64) -> (u64, u64) {
    if e == 1 {
        (1, n)
    }
    else if e % 2 == 0 {
        let (s, p) = sum_pow(n, e/2, d);
        (s * (1 + p) % d, p * p % d)
    }
    else {
        let (s, p) = sum_pow(n, e-1, d);
        ((1 + n * s) % d, p * n % d)
    }
}

fn f(N: u64) -> u64 {
    let (s, p) = sum_pow(4, N+1, D);
    s
}

fn main() {
    let N: u64 = read();
    println!("{}", f(N))
}