AtCoder Beginner Contest 328振り返り

A - Not Too Hard

X以下の数の合計を求めるため、フィルタをかけてから合計する必要がある。

use proconio::input;

fn main() {
    input! {
        n: usize,
        x: usize,
        s: [usize; n]
    }

    let ans: usize = s.iter().filter(|&&a| a <= x).sum();
    println!("{}", ans);
}

B - 11/11

全ての数を文字列に変換して考える。最初の1文字目を取得し、全ての文字が一文字目と一致する場合にぞろ目となる。

use proconio::input;

fn main() {
    input! {
        n: usize,
        d: [usize; n],
    }

    let ans: usize = (0..n)
        .map(|i| {
            let a: Vec<_> = (i + 1).to_string().chars().collect();
            let t = a[0];

            if !a.iter().all(|&a| a == t) {
                return 0;
            }

            let ans = (0..d[i])
                .filter(|&j| {
                    let b: Vec<_> = (j + 1).to_string().chars().collect();
                    if !b.iter().all(|&b| b == t) {
                        return false;
                    }
                    return true;
                })
                .count();

            return ans;
        })
        .sum();

    println!("{}", ans);
}

C - Consecutive

O(NQ)では時間内に処理できないと考え、累積和を使って解く方法を考える。
ここで境界に気をつけることが重要。

use proconio::{
    derive_readable, input,
    marker::{Chars, Usize1},
};

fn main() {
    #[derive(Debug)]
    #[derive_readable]
    struct LR {
        l: Usize1,
        r: Usize1,
    }

    input! {
        n: usize,
        q: usize,
        s: Chars,
        lr: [LR; q],
    }

    let mut memo = vec![0; n];

    (1..n).for_each(|i| {
        let c1 = s[i];
        let c2 = s[i - 1];
        if c1 == c2 {
            memo[i] = memo[i - 1] + 1;
        } else {
            memo[i] = memo[i - 1];
        }
    });

    lr.iter().for_each(|&LR { l, r }| {
        let ans = memo[r] - memo[l];
        println!("{}", ans);
    });
}

D - Take ABC

この問題も解けたが、少し手間取った。
最初は先頭から順に判定を行い、追加削除を高速に行うためにLinkedListを使おうとしたが、実装が難しく時間がかかってしまった。
代わりに、配列の末尾に要素を追加していき、"ABC"になったら3つ分を削除するという方法を採用することで、効率よく実装できる。

use proconio::{input, marker::Chars};

fn main() {
    input! {
        s: Chars,
    }

    let mut q = Vec::new();

    for i in 0..s.len() {
        q.push(s[i]);

        let len = q.len();
        if len >= 3 {
            if q[len - 1] == 'C' && q[len - 2] == 'B' && q[len - 3] == 'A' {
                for _ in 0..3 {
                    q.pop();
                }
            }
        }
    }

    let str: String = q.iter().collect();
    println!("{}", str);
}

E - Modulo MST

この問題は30分ほど時間をかけましたが、解くことができませんでした。
重みの問題なので最初はダイクストラ法を使えば解けそうだと考えましたが、違う方針で解かなければならない問題でした。
また、Nが小さいので全探索を行えば解けたということも気づくべきでした。
この問題のような全域木の辺の本数はN-1という事実も覚えておく必要があります。

use itertools::Itertools;
use petgraph::graph::*;
use petgraph::visit::*;
use proconio::{derive_readable, input, marker::Usize1};

fn main() {
    #[derive(Debug)]
    #[derive_readable]
    struct UVW {
        u: Usize1,
        v: Usize1,
        w: usize,
    }

    input! {
        n: usize,
        m: usize,
        k: usize,
        uvw: [UVW; m],
    }

    let ans: usize = (0..m)
        .combinations(n - 1)
        .map(|edges| {
            let g: Graph<usize, usize, petgraph::Undirected, usize> =
                UnGraph::from_edges(edges.iter().map(|&i| {
                    let UVW { u, v, w } = uvw[i];
                    (u, v, w)
                }));

            let mut dfs = Dfs::new(&g, g.node_references().next().unwrap().0);
            let mut visited = g.visit_map();
            while let Some(nx) = dfs.next(&g) {
                visited.visit(nx);
            }

            if visited.count_ones(0..visited.len()) != n {
                return usize::MAX;
            } else {
                let total: usize = g.edge_weights().sum();
                return total % k;
            }
        })
        .min()
        .unwrap();
    println!("{}", ans);
}

総括

E問題は自分の実力で解ける問題だった。

グラフや連結リストについてはもう少し慣れておきたい。