AtCoder Beginner Contest 294 - zeronosu77108’s blog

AtCoder Beginner Contest 294 です。

A,B,C,D,E,F,G のノーペナ 59:54 7 完でした。 2回目のカンスト。初めてのカンストは嘘通してたので、今回はまともに解いて初カンスト？（そうなら嬉しい）実は 21:00 まで寝落ちしていて、寝起き過ぎて出るか迷っていたんだけど出て良かった。

A - Filter

問題文

数列が与えられるので、偶数だけ抜き出して出力する。

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

    println!("{}", a.iter().filter(|&x| x%2 == 0).join(" "));
}

提出

B - ASCII Art

問題文

$ 1 $ 以上ならその値に合わせて 'A' とかに変換する。

fn main() {
    input! {
        h : usize,
        w : usize,
        a : [[u8; w]; h]
    }

    let mut b = vec![vec!['.'; w]; h];
    for i in 0..h { for j in 0..w {
        if a[i][j] == 0 { continue }
        b[i][j] = (b'A' + a[i][j] - 1) as char;
    }}

    println!("{}", b.iter().map(|b| b.iter().join("")).join("\n"));;;;;;;
}

提出

C - Merge Sequences

問題文

マージの過程を良い感じにする感じ。$A$ を見ているインデックスと $B$ を見ているインデックスを作って、小さい方からインデックスを進めていくと良い。終端の処理がめんどくさいので雑に書く。

fn main() {
    input! {
        n : usize,
        m : usize,
        a : [usize; n],
        b : [usize; m]
    }

    let mut ans1 = vec![0; n];
    let mut ans2 = vec![0; m];

    let mut i = 0;
    let mut j = 0;
    let mut now = 1;

    while i < n && j < m {
        if a[i] < b[j] {
            ans1[i] = now;
            i += 1;
        } else if a[i] > b[j] {
            ans2[j] = now;
            j += 1;
        }
        now += 1;
    }
    while i < n {
        ans1[i] = now;
        i += 1;
        now += 1;
    }
    while j < m {
        ans2[j] = now;
        j += 1;
        now += 1;
    }

    println!("{}\n{}", ans1.iter().join(" "), ans2.iter().join(" "));
}

提出

D - Bank

問題文

呼ばれたとか、受付に行くとかちょっとだけ読みにくい…。まだ呼ばれていない人を BtreeSet とかで管理して小さい順に取り出す（これは Deque とかで良かったかも）。既に呼ばれたが受付に行っていない人も BtreeSet で管理して良い感じに出力する。

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

    let mut no : BTreeSet<_> = (1..=n).collect();
    let mut que = BTreeSet::new();

    let mut ans = Vec::with_capacity(q);
    for _ in 0..q {
        input! { t : u8 }
        match t {
            1 => {
                let min = no.iter().next().cloned().unwrap();
                no.remove(&min);
                que.insert(min);
            }
            2 => {
                input! { x : usize }
                que.remove(&x);
            }
            3 => {
                let min = que.iter().next().cloned().unwrap();
                ans.push(min);
            }
            _ => unreachable!()
        }
    }

    println!("{}", ans.iter().join(" "));
}

提出

E - 2xN Grid

問題文

ランレングス圧縮されたものが渡されるので、元の数列で $A_i = B_i$ となるような $i$ の個数を求める。

C問題と同じ感じで、それぞれインデックスを持って短い方を進めつつ同じ奴があったらその長さを計算していくと良い。

fn main() {
    input! {
        l : usize,
        n1 : usize,
        n2 : usize,
        vl1 : [(usize, usize); n1],
        vl2 : [(usize, usize); n2]
    }

    let mut nowi = 0;
    let mut leni = 0;
    let mut nowj = 0;
    let mut lenj = 0;
    
    let mut ans : usize = 0;
    loop {
        let (v1, len1) = vl1[nowi];
        let (v2, len2) = vl2[nowj];

         if leni + len1 >= lenj + len2 {
             if v1 == v2 {
                ans += (leni + len1).min(lenj + len2) - leni.max(lenj);
             }
             lenj += len2;
             nowj += 1;
         } else {
            if v1 == v2 {
                ans += (leni + len1).min(lenj + len2) - lenj.max(leni);
            }
            leni += len1;
            nowi += 1;
         }

        if nowi >= n1 || nowj >= n2 { break }
    }

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

提出

F - Sugar Water 2

問題文

二分探索したら良さそうですね～、どうやったら判定できるんですか？食塩水ありがとう…をしていた。

$ x \% $ にするときに、何g 足りない（余っている）か計算しておいてソートしておけば、$ x \% $ の砂糖水を作る事ができる組合せが何個あるか適当に計算できる。

$A, B$ の分も計算してソートしてたけど、別にそんなことしなくて良かったな。

fn main() {
    input! {
        n : usize,
        mm : usize,
        k : usize,
        ab : [(f64, f64); n],
        cd : [(f64, f64); mm]
    }

    let mut l = 0.0;
    let mut r = 100.0;

    for _ in 0..100 {
        let m = (l + r) / 2.0;

        let mut aa = Vec::with_capacity(n);
        for &(a, b) in ab.iter() {
            let p = a / (a + b) * 100.;
            aa.push((a + b) * (p - m));
        }
        aa.sort_by(|a, b| a.partial_cmp(b).unwrap());

        let mut cc = Vec::new();
        for &(c, d) in cd.iter() {
            let p = c / (c + d) * 100.;
            cc.push((c + d) * (p - m));
        }
        cc.sort_by(|a, b| a.partial_cmp(b).unwrap());


        let mut cnt = 0;
        for &a in aa.iter() {
            let index = cc.lower_bound_by(|&c| c.partial_cmp(&(-a)).unwrap());
            cnt += mm - index;
        }

        if cnt >= k {
            l = m;
        } else {
            r = m;
        }
    }

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

提出

G - Distance Queries on a Tree

問題文

HLD してセグ木で和を求めると良い。遥か昔に作ったライブラリで使い方覚えていなかったが、名前と引数の雰囲気で実装できた。

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

    let mut  hld = HeavyLightDecomposition::new(n);
    for &(u,v, w) in edges.iter() {
        hld.add_edge(u, v);
    }

    hld.build(0);

    def_monoid!(M, usize, 0, |x, y| x + y);
    let mut seg = SegmentTree::<M>::new(n);
    for &(u, v, w) in edges.iter() {
        hld.for_each_edge(u, v, |l, r| {
            seg.set(l.min(r), w);
        });
    }

    let mut ans = Vec::with_capacity(q);
    for _ in 0..q {
        input! { t : u8 }
        match t {
            1 => {
                input! { i:Usize1, w:usize }
                hld.for_each_edge(edges[i].0, edges[i].1, |l, r| {
                    seg.set(l.max(r), w);
                });
            }
            2 => {
                input! { u:Usize1, v:Usize1 }
                let mut t = 0;
                hld.for_each_edge(u, v, |l, r| {
                    t += seg.fold(l..=r);
                });
                ans.push(t);
            }
            _ => unreachable!(),
        }
    }

    println!("{}", ans.iter().join("\n"));
}