AtCoder Beginner Contest 333 振り返り

A - Three Threes

繰り返すだけ。

use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    let str = (0..n).map(|_| n.to_string()).join("");
    println!("{}", str);
}

B - Pentagon

一瞬混乱したけど、数値をu8にキャストすると楽っぽい。

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

fn main() {
    input! {
        s: Bytes,
        t: Bytes,
    }

    let s: Vec<_> = s.iter().map(|x| (x - 'A' as u8) as i32).collect();
    let t: Vec<_> = t.iter().map(|x| (x - 'A' as u8) as i32).collect();

    fn len(a: i32, b: i32) -> i32 {
        let diff = (a - b).abs();

        if diff == 1 || diff == 4 {
            return 1;
        }

        return 2;
    }

    if len(s[0], s[1]) == len(t[0], t[1]) {
        println!("Yes");
    } else {
        println!("No");
    }
}

C - Repunit Trio

N=333が出ているのがヒント。

use itertools::{iproduct, Itertools};
use proconio::input;
use std::collections::BTreeSet;

fn main() {
    input! {
        n: usize,
    }

    let reps: Vec<_> = (1..=12)
        .map(|x| {
            let s = (0..x).map(|_| "1").join("");
            let a: i64 = s.parse().unwrap();
            return a;
        })
        .collect();

    let set = BTreeSet::from_iter(
        iproduct!(0..12, 0..12, 0..12).map(|(i, j, k)| reps[i] + reps[j] + reps[k]),
    );
    let vec: Vec<_> = set.iter().collect();
    println!("{}", vec[n - 1]);
}

D - Erase Leaves

petgraphのDfsの使えば計算できる。

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

fn main() {
    input! {
        n: usize,
        uvs: [(Usize1, Usize1); n - 1]
    }

    let g: Graph<usize, usize, Undirected, usize> = UnGraph::from_edges(&uvs);
    let costs: Vec<_> = g
        .neighbors(node_index(0))
        .map(|i| {
            let mut cost = 0;
            let mut dfs = Dfs::new(&g, i);
            while let Some(i) = dfs.stack.pop() {
                if !dfs.discovered.visit(i) {
                    continue;
                }

                if i.index() == 0 {
                    continue;
                }

                cost += 1;

                g.neighbors(i)
                    .filter(|j| !dfs.discovered.is_visited(j))
                    .for_each(|j| {
                        dfs.stack.push(j);
                    });
            }
            cost
        })
        .collect();

    let ans = costs.iter().sum::<usize>() - costs.iter().max().unwrap() + 1;
    println!("{}", ans);
}