AtCoder Beginner Contest 252 - zeronosu77108’s blog

6完ペナ込み 97:22 でした（5ペナ）。 6完したのに激渋なんですが…。

A - ASCII code

文字コードが与えられるので変換して出力します。

fn main() {
    input! {
        n : u8
    }
 
    println!("{}", n as char);
}

提出

B - Takahashi's Failure

問題文

嫌いな食べ物のうち、1つでもおいしさ最大のものがあったら、嫌いな食べ物を食べる可能性があります。

先に $A$ の最大値を求めておいて、 $A_{B_i}$ が最大値と一致するか見たら良いです。

fn main() {
    input! {
        n : usize,
        k : usize,
        a : [usize; n],
        b : [Usize1; k]
    }
 
    let max = *a.iter().max().unwrap();
 
    println!("{}", if b.iter().any(|&i| a[i] == max) {"Yes"} else {"No"});
}

提出

C - Slot Strategy

問題文

どれか一つの数字に揃えたくて、最短で揃えたら何秒になりますか？っていう問題。

$N \leq 100$ と小さいので、一番近い奴にどんどん揃えていけば良いです。

fn main() {
    input! {
        n : usize,
        s : [Bytes; n]
    }
    
    let mut ans = std::usize::MAX;
    for i in 0..10 { // i に揃える
        let mut used = vec![false; n];
        let mut tmp = 0;
        let mut now = 0;
        let mut a = 0;
        for k in 0..n {
            let mut min = std::usize::MAX;
 
            for (j, s) in s.iter().enumerate() {
                if used[j] { continue }
                let index = s.iter().position(|&c| (c-b'0') == i as u8).unwrap();
                let t = if now%10 < index || k==0 && index==0 { index - now%10 } else { 10 - now%10 + index };
                if t < min { min=t; a=j; }
            }
 
            now += min;
            used[a] = true; 
        }
        ans = ans.min(now);
    }
 
    println!("{}", ans);
}

提出

D - Distinct Trio

問題文

異なるものを 3つ選ぶ方法を直接求めるのは難しそうです。よって、どれかが同じになるものを考えて、全体から引けば良さそうです。

$N$ 個の中から、3個を選ぶ組合せは、 ${} _ n \mathrm{C} _ 3$ なので、 $\frac{n \times (n-1) \times (n-2)}{3!} $ になります。

重複する場合を数えたいので、まず各数が何個あるのか数えます。ある数$i$が $c$個あるとき、 3個のうち $i$ が 2個選ばれる場合の数は、 ${} _ c \mathrm{C} _ 2 \times (n - c)$ です。 3個選ばれる場合は、 ${} _ c \mathrm{C} _ 3 $ です。よって、これらを引けば良いです。

fn main() {
    input! {
        n : usize,
        a : [usize; n]
    }
 
    let mut ans = n * (n-1) / 2 * (n-2) / 3;
 
    let mut mp = BTreeMap::new();
    for &a in a.iter() { *mp.entry(a).or_insert(0) += 1; }
 
    for (_, &c) in mp.iter() {
        ans -= c * (c-1) / 2 * (n - c);
        ans -= c * (c-1) / 2 * (c-2) / 3;
    }
 
    println!("{}", ans);
}

提出

E - Road Reduction

問題文

都市1からの最短経路となる辺だけを残して最小全域木にしてくださいという問題。

ダイクストラして、その経路復元をしたら良いです。ちゃんと復元するとめんどくさいので、頂点の最短距離が確定したときにそこに来るために使用した辺を保存していけば良いです。

最後の出力、辺の数で確認しなければいけないのに、頂点数でチェックしてペナりました。

fn main() {
    input! {
        n : usize,
        m : usize,
        edges : [(Usize1, Usize1, usize); m]
    }
 
    let mut g = vec![vec![]; n];
    for (i, &(a,b,c)) in edges.iter().enumerate() {
        g[a].push((b,c,i));
        g[b].push((a,c,i));
    }
 
    let mut used = vec![false; m];
    dijkstra(0, &g, &mut used);
 
    println!("{}", (1..=m).filter(|i| used[i-1]).join(" "))
}
 
fn dijkstra<T>(s:usize, g:&Vec<Vec<(usize,T, usize)>>, used:&mut Vec<bool>) -> Vec<Option<T>>
where
    T : Clone + Copy + num::Zero + std::ops::Add + std::cmp::Ord
{
    let mut dist = vec![None; g.len()];
    dist[s] = Some(std::cmp::Reverse(T::zero()));
    let mut pq = std::collections::BinaryHeap::from(vec![(std::cmp::Reverse(T::zero()), s, None)]);
 
    while let Some((std::cmp::Reverse(c),v, i)) = pq.pop() {
        if let Some(std::cmp::Reverse(d)) = *&dist[v] {
            if d < c { continue }
            if let Some(i) = i { used[i] = true; }
            for &(u, c, j) in g[v].iter() {
                if chmax(&mut dist[u], Some(std::cmp::Reverse(d + c))) {
                    pq.push((dist[u].unwrap().into(), u, Some(j)));
                }
            }
        }
    }
 
    dist.into_iter().map(|d| match d {Some(std::cmp::Reverse(x)) => Some(x), _ => None}).collect()
}

提出

F - Bread

問題文

大きいやつを何度も切るのは嫌なので、良い感じに小さくしたいです。これは逆向きに考えて良くて、小さい方からマージしていけば良いです。

後は、 $L - \sum A_i$ の分を上手く考えれば良いです。$L - \sum A_i = 0$ のときは何もしなくて良くて、$L - \sum A_i > 0$ の時は、 $L - \sum A_i$ もどこかのタイミングで切り出してやらないといけないので、切る候補の中に追加します。 ← これに気付くのに時間かかりすぎた（4ペナ…）。

fn main() {
    input! {
        n : usize,
        l : usize,
        a : [usize; n]
    }
 
    let mut pq : BinaryHeap<_> = a.iter().map(|&a| Reverse(a)).collect();
 
    let sum = a.iter().sum::<usize>();
    if l != sum { pq.push(Reverse(l - sum)); }
 
    let mut ans = 0;
    while pq.len() > 1 {
        let Reverse(a) = pq.pop().unwrap();
        let Reverse(b) = pq.pop().unwrap();
        ans += a + b;
        pq.push(Reverse(a + b));
    }
 
    println!("{}", ans );
}