AtCoder Beginner Contest 270 D

https://atcoder.jp/contests/abc270/tasks/abc270_d

残りの石の数に対して、どちらも最善を尽くしたとき、先番がいくつ取れるかをDPにします。
ふつうにtake_whileが使えますね。

// Stones
#![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() -> (usize, Vec<usize>) {
    let v = read_vec();
    let N = v[0];
    let A = read_vec();
    (N, A)
}

fn f(N: usize, A: Vec<usize>) -> usize {
    let mut dp: Vec<usize> = (0..(N+1)).map(|_| 0).collect();
    for n in 1..(N+1) {
        dp[n] = A.iter().take_while(|&a| a <= &n).
                            map(|&a| n - dp[n-a]).max().unwrap();
    }
    dp[N]
}

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

AtCoder Beginner Contest 271 D

https://atcoder.jp/contests/abc271/tasks/abc271_d

カードの組と和でDPすればいいです。この時、1歩前の和を記録しておくとDPが終わった後にtrace backできて文字列を作ることができます。
後ろから追加していくので、あとから逆順の文字列にします。

// Flip and Adjust
#![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() -> (i32, Vec<(i32, i32)>) {
    let v = read_vec();
    let N = v[0];
    let S = v[1];
    let ab = (0..N).map(|_| { let w = read_vec(); (w[0], w[1]) }).
                                            collect::<Vec<(i32, i32)>>();
    (S, ab)
}

fn f(S: i32, ab: Vec<(i32, i32)>) -> (bool, String) {
    let N = ab.len();
    let max_sum = ab.iter().map(|(a, b)| max(*a, *b)).sum::<i32>();
    if S > max_sum {
        return (false, "".to_string())
    }
    
    let mut dp = (0..(N+1)).map(|_| (0..(max_sum+1)).
                            map(|_| -1).collect::<Vec<i32>>()).
                            collect::<Vec<Vec<i32>>>();
    dp[0][0] = 0;
    for (i, (a, b)) in ab.iter().enumerate() {
        for s in 0..(max_sum as usize + 1) {
            let s_prev = dp[i][s];
            if (i == 0 && s != 0) || (i > 0 && s_prev == -1) {
                continue
            }
            dp[i+1][s+(*a as usize)] = s as i32;
            dp[i+1][s+(*b as usize)] = s as i32
        }
    }
    
    if dp[N][S as usize] == -1 {
        return (false, "".to_string())
    }
    
    let mut ht_rev = String::from("");
    let mut s = S;
    for i in (0..N).rev() {
        let (a, _b) = ab[i];
        let d = s - dp[i+1][s as usize];
        ht_rev += if d == a { "H" } else { "T" };
        s = dp[i+1][s as usize]
    }
    
    let ht: String = ht_rev.chars().rev().collect();
    (true, ht)
}

fn main() {
    let (S, ab) = read_input();
    match f(S, ab) {
        (true, ht) => println!("Yes\n{}", ht),
        (false, _) => println!("No")
    }
}

AtCoder Beginner Contest 282 D

https://atcoder.jp/contests/abc282/tasks/abc282_d

連結成分に分けて、隣り合うノードを白と黒に塗り分けます。塗り分けられなかったら二部グラフではありません。そして、連結成分の中と連結成分の間にエッジをいくつ作れるかを数えます。

// Make Bipartite 2
#![allow(non_snake_case)]

use std::collections::HashMap;

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 read_input() -> (usize, Vec<(usize, usize)>) {
    let edge = |_| -> (usize, usize) {
        let v: Vec<usize> = read_vec();
        (v[0] - 1, v[1] - 1)
    };
    let v: Vec<usize> = read_vec();
    let N = v[0];
    let M = v[1];
    let edges = (0..M).map(edge).collect::<Vec<(usize, usize)>>();
    (N, edges)
}

type Graph = Vec<Vec<usize>>;

fn make_graph(N: usize, edges: Vec<(usize, usize)>) -> Graph {
    let mut graph: Graph = (0..N).map(|_| vec![]).collect();
    for (u, v) in edges.iter() {
        graph[*u].push(*v);
        graph[*v].push(*u)
    }
    graph
}

#[derive(PartialEq)]
enum Color {
    White, Black
}

fn reverse_color(color: &Color) -> Color {
    match *color {
        Color::White => Color::Black,
        Color::Black => Color::White,
    }
}

fn divide_into_connected(graph: &Graph) -> Vec<HashMap<usize, Color>> {
    let N = graph.len();
    let mut maps = Vec::<HashMap<usize, Color>>::new();
    let mut visited = (0..N).map(|_| false).collect::<Vec<bool>>();
    for v0 in 0..N {
        if visited[v0] {
            continue
        }
        
        let mut m = HashMap::<usize, Color>::new();
        m.insert(v0, Color::White);
        let mut stack: Vec<(usize, Color)> = vec![(v0, Color::White)];
        loop {
            match stack.pop() {
                Some((v, color)) => {
                    for v1 in graph.get(v).unwrap().iter() {
                        match m.get(&v1) {
                            Some(color1) => {
                                if *color1 == color {
                                    // 2部グラフでない
                                    return Vec::<HashMap<usize, Color>>::new();
                                }
                            },
                            None => {
                                stack.push((*v1, reverse_color(&color)));
                                m.insert(*v1, reverse_color(&color));
                                visited[*v1] = true
                            }
                        }
                    }
                },
                None => break
            }
        }
        maps.push(m)
    }
    maps
}

fn count_inner_connected(m: &HashMap<usize, Color>) -> usize {
    let num_white = m.iter().filter(|(_, c)| **c == Color::White).count();
    let num_black = m.iter().filter(|(_, c)| **c == Color::Black).count();
    num_white * num_black
}

fn count_inter_connected(maps: &Vec<HashMap<usize, Color>>) -> usize {
    let sum: usize = maps.iter().map(|m| m.len()).sum();
    let sum_squares: usize = maps.iter().map(|m| m.len() * m.len()).sum();
    (sum * sum - sum_squares) / 2
}

fn f(N: usize, edges: Vec<(usize, usize)>) -> usize {
    let M = edges.len();
    let graph = make_graph(N, edges);
    let maps = divide_into_connected(&graph);
    if maps.is_empty() {
        return 0
    }
    
    maps.iter().map(|m| count_inner_connected(m)).sum::<usize>() +
                            count_inter_connected(&maps) - M
}

fn main() {
    let v = read_input();
    println!("{}", f(v.0, v.1))
}

AtCoder Beginner Contest 276 D

https://atcoder.jp/contests/abc276/tasks/abc276_d

AのgcdにAの各要素が何回割ってたどり着くかをカウントします。
reduceって無いんですね。foldだとgcdはちょっと面倒ですよね。

// Divide by 2 or 3
#![allow(non_snake_case)]

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 read_input() -> Vec<i32> {
    let _N: usize = read();
    let A = read_vec();
    A
}

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { gcd(b, a % b) }
}

fn gcd_vec(A: &Vec<i32>) -> i32 {
    let mut iter = A.iter();
    match iter.next() {
        Some(&e0) => iter.fold(e0, |e, &f| gcd(e, f)),
        None      => 1
    }
}

fn num_divs23(e: i32) -> i32 {
    if e == 1 {
        0
    }
    else if e % 2 == 0 {
        num_divs23(e / 2) + 1
    }
    else if e % 3 == 0 {
        num_divs23(e / 3) + 1
    }
    else {
        -100    // 再帰でも負を返す
    }
}

fn f(A: Vec<i32>) -> i32 {
    let d = gcd_vec(&A);
    let mut counter: i32 = 0;
    for e in A.into_iter() {
        if e % d != 0 {
            return -1
        }
        else {
            let n = num_divs23(e / d);
            if n < 0 {
                return -1
            }
            else {
                counter += n
            }
        }
    }
    counter
}

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

AtCoder Beginner Contest 277 D

https://atcoder.jp/contests/abc277/tasks/abc277_d

Aをソートして、グループ化します。あとは最初と最後がくっつくかですね。

// Takahashi's Solitaire
#![allow(non_snake_case)]

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 read_input() -> (usize, Vec<usize>) {
    let v: Vec<usize> = read_vec();
    let _N = v[0];
    let M = v[1];
    let A = read_vec();
    (M, A)
}

fn make_regions(A: &Vec<usize>, M: usize) -> Vec<(usize, usize, usize)> {
    let mut B = A.clone();
    B.sort();
    
    let mut regions = Vec::<(usize, usize, usize)>::new();
    let mut first: usize = M;
    let mut last: usize = 0;
    let mut s: usize = 0;
    for &a in B.iter() {
        if first == M {     // start
            first = a;
            s = a;
        }
        else if a == last - 1 || a == last {
            s += a;
        }
        else {
            regions.push((first, last, s));
            first = a;
            s = a;
        }
        last = a + 1;
    }
    regions.push((first, last, s));
    let (first1, last1, s1) = regions.first().unwrap();
    let (first2, last2, s2) = regions.last().unwrap();
    if *first1 == 0 && *last2 == M && regions.len() > 1 {
        regions[0] = (*first2, *last1, s1 + s2);
        regions.pop();
    }
    regions
}

fn f(M: usize, A: Vec<usize>) -> usize {
    let regions = make_regions(&A, M);
    let max_sum = regions.iter().map(|(_, _, s)| s).max().unwrap();
    A.iter().sum::<usize>() - max_sum
}

fn main() {
    let v = read_input();
    println!("{}", f(v.0, v.1))
}

AtCoder Beginner Contest 281 D

https://atcoder.jp/contests/abc281/tasks/abc281_d

キーが個数と和のDの剰余、値を和の最大値とするDPですね。

// All Assign Point Add
#![allow(non_snake_case)]

use std::collections::HashMap;

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 read_input() -> (usize, usize, Vec<usize>) {
    let v: Vec<usize> = read_vec();
    let K = v[1];
    let D = v[2];
    let A = read_vec();
    (K, D, A)
}

fn f(K: usize, D: usize, A: Vec<usize>) -> i64 {
    let mut dic = HashMap::<(usize, usize), usize>::new();
    dic.insert((0, 0), 0);
    for a in A.into_iter() {
        let mut new_dic = dic.iter().map(|((r, n), &m)| ((*r, *n), m)).
                            collect::<HashMap<(usize, usize), usize>>();
        for ((n, r), &max_value) in dic.iter() {
            let key = (n + 1, (r + a) % D);
            match new_dic.get(&key) {
                Some(&v) => if max_value + a > v {
                                    new_dic.insert(key, max_value + a); },
                None     => { new_dic.insert(key, max_value + a); }
            }
        }
        dic = new_dic
    }
    
    match dic.get(&(K, 0)) {
        Some(&v) => v as i64,
        None     => -1
    }
}

fn main() {
    let v = read_input();
    println!("{}", f(v.0, v.1, v.2))
}

AtCoder Beginner Contest 278 D

https://atcoder.jp/contests/abc278/tasks/abc278_d

HashMapを使えば簡単ですね。

// All Assign Point Add
#![allow(non_snake_case)]

use std::collections::HashMap;

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 read_input() -> (Vec<usize>, Vec<Vec<usize>>) {
    let _N: usize = read();
    let A = read_vec();
    let Q: usize = read();
    let queries = (0..Q).map(|_| read_vec()).collect::<Vec<Vec<usize>>>();
    (A, queries)
}

struct Array {
    base: usize,
    M: HashMap<usize, usize>
}

impl Array {
    fn query(&mut self, q: Vec<usize>) {
        match q[0] {
            1 => self.set_all_value(q[1]),
            2 => self.set_value(q[1], q[2]),
            3 => println!("{}", self.get_value(q[1])),
            _ => ()
        }
    }
    
    fn set_all_value(&mut self, x: usize) {
        self.base = x;
        self.M = HashMap::<usize, usize>::new()
    }
    
    fn set_value(&mut self, i: usize, x: usize) {
        let v = self.M.entry(i).or_insert(0);
        *v += x
    }
    
    fn get_value(&self, i: usize) -> usize {
        match self.M.get(&i) {
            Some(&e) => e + self.base,
            None     => self.base
        }
    }
}

fn f(A: Vec<usize>, queries: Vec<Vec<usize>>) {
    let M = (0..A.len()).map(|i| (i+1, A[i])).collect::<HashMap<usize, usize>>();
    let mut a = Array { base: 0, M: M };
    for q in queries.into_iter() {
        a.query(q)
    }
}

fn main() {
    let v = read_input();
    f(v.0, v.1)
}