← ブログ一覧に戻る

AtCoder Beginner Contest 382

#ABC #AtCoder

AtCoder Beginner Contest 382 です。 Unrated 参加で、 ABCDFの5完 81:05（0ペナ）でした。

A - Daily Cookie

問題文

いくつかのクッキー入りの箱と空箱があるのでえ、クッキーを$D$個食べたら空箱は何個になるかという問題。 制約で$D$個以上クッキーが入った箱があるので、空箱の数+$D$が答え。

fn main() {
    input! {
        n : usize,
        d : usize,
        s : Chars
    }    
    
    let mut cnt = s.iter().filter(|&&c| c == '.').count();
    
    println!("{}", cnt + d);
}

提出



B - Daily Cookie 2

問題文

Aと似たような問題。箱の列が与えられるので右側から$D$個食べたあとの状態を出力してくださいという問題。 後ろからやるのがめんどくさかったので、 reverse して前から食べていってさらに reverse して出力した。

fn main() {
    input! {
        n : usize,
        mut d : usize,
        mut s : Chars
    }
    
    s.reverse();
    for i in 0..n {
        if d == 0 { break }
        if s[i] == '@' { s[i] = '.'; d -= 1; }
    }
    println!("{}", s.iter().rev().join(""));
}

提出



C - Kaiten Sushi

問題文

ベルトコンベアの前に人が居て、美食度が決まっている。 その美食度以上の寿司が来たらその人が食べるので、$M$個与えられる寿司が誰に食べられるかを求める問題。

$B$ を降順に並べて、$A_i$ を順番に見ていって、食べられるだけお寿司を食べるという感じで解ける。 $B$ は index と一緒にソートしておく。

use itertools::Itertools;
use proconio::input;
use superslice::Ext;

fn main() {
    input! {
        n : usize,
        m : usize,
        a : [usize; n],
        mut b : [usize; m]
    }
    
    let b = b.into_iter().enumerate().map(|(i, x)| (x, i)).sorted().rev().collect::<Vec<_>>();
    let mut now = 0;
    let mut ans = vec![-1; m];
    for (i, a) in a.iter().enumerate() {
        while now<m && b[now].0 >= *a {
            ans[b[now].1] = (i + 1) as i64;
            now+=1;
        }
    }
    
    println!("{}", ans.iter().join("\n"));
}

提出



D - Keep Distance

問題文

適当に範囲絞って DFS する問題。 最初雑に書いたら 4900 ms とかになってて、怖いなぁと思って少し絞って書いたら 100 ms とかになった。

fn main() {
    input! {
        n : usize,
        m : usize
    }
    
    let mut ans = vec![];
    let mut tmp = vec![];
    for i in 1..=11 {
        tmp.push(i);
        f(i, n, m, &mut tmp, &mut ans);
        tmp.pop();
    }
    
    println!("{}\n{}", ans.len(), ans.iter().join("\n"));
}

fn f(i: usize, n: usize, m:usize, tmp: &mut Vec<usize>, ans: &mut Vec<String>) {
    if tmp.len() == n {
        ans.push(tmp.iter().join(" "));
        return;
    }
    
    
    for j in i+10..=i+20 {
        if j + (n-tmp.len()).saturating_sub(1) * 10 > m { break }
        tmp.push(j);
        f(j, n, m, tmp, ans);
        tmp.pop();
    }
}

提出



E - Expansion Packs

問題文

$N$枚のカードが入ったパックがあって、$i$枚目に入っているカードがレアな確率が$P_i$としたときに、$X$枚以上レアカードを手に入れるまで開封するパックの期待値を求める問題。

最初、ちょうど$1$枚のレアカードを手に入れる確率、ちょうど$2$枚のを手に入れる確率、$\cdots$を求めようとしていたんだけど、なんか上手く計算できず…。 結局考え直したらバラバラに hit を計算していたけど、式がおかしかった。

$hit[i] = hit[i] \times (1 - p_i / 100) + hit[i - 1] \times (p_i / 100)$ という感じで計算していけば良い。

fn main() {
    input! {
        n : usize,
        x : usize,
        p : [f64; n]
    }
    
    let mut hit = vec![0.0; n + 1];
    hit[0] = 1.0;
    for &p in p.iter() {
        for i in (1..=n).rev() {
            hit[i] = hit[i] * (1. - p/100.) + hit[i-1] * p/100.;
        }
        hit[0] *= 1. - p/100.;
    }
    
    println!("{}", f(n, x, &hit));
}

#[memoise(x<=5000)]
fn f(n:usize, x:usize, hit:&Vec<f64>) -> f64 {
    if x == 0 { return 0.0; }
    let mut res = 1.;
    
    for i in 1..=n {
        res += f(n, x.saturating_sub(i), hit) * hit[i];
    }

    res / (1. - hit[0])
}

提出



F - Falling Bars

問題文

テトリスみたいな問題。横長の長方形がいくつかあるから落ち物シミュレーションをしてくださいという問題。 範囲適用範囲最大値の遅延セグ木でいくつ積み重なっているかを管理した。

fn main() {
    input! {
        h : usize,
        w : usize,
        n : usize,
        mut rcl : [(Usize1, Usize1, usize); n]
    }
    
    let mut rcl = rcl.into_iter().enumerate().map(|(i, (r, c, l))| (r, c, l, i)).collect_vec();
    rcl.sort_by_key(|&(r, _, _, _)| Reverse(r));

    let mut seg = LazySegmentTree::<M>::new(w + 1);
    let mut ans = vec![0; n];
    for (r, c, l, i) in rcl {
        let m = seg.fold(c..c+l);
        ans[i] = h - m;
        seg.update(c..c+l, m + 1);
    }
    
    println!("{}", ans.iter().join("\n"));
}

提出



https://atcoder.jp/contests/abc382/tasks/abc382_g

問題文

見てない



まとめ

今回はお外に居たので Unrated 参加したんだけど、 E 問題に苦手な問題があり冷え回避できた回だった。 D問題に時間かけすぎている感があるのでもう少し速く解けるようにしたい。

← ブログ一覧に戻る