AtCoder Beginner Contest 294をRustで解く(A-Gまで)

[abc294](https://atcoder.jp/contests/abc294)お疲れ様でした！早速解説です！！(A-Gまで)
[公式解説](https://atcoder.jp/contests/abc294/editorial)が豊富なので、こちらの記事では簡単に記載しています。

質問、感想はこの記事のコメントでも、[twitter](https://twitter.com/okaponta_)でも、大歓迎です！:muscle:

## [問題A](https://atcoder.jp/contests/abc294/tasks/abc294_a)

### 考察

特定の条件に合致するものを取り出すには、`filter`を使うと便利です。
出力の際には、`Itertools`の`join`を使用するといい感じに書けます。

### 解答

https://atcoder.jp/contests/abc294/submissions/39848859

```Rust
use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }
    println!("{}", a.into_iter().filter(|i| i % 2 == 0).join(" "));
}
```

## [問題B](https://atcoder.jp/contests/abc294/tasks/abc294_b)

### 考察

数字 -> アルファベットの変換を実施する問題です。
`(b'A' + (数字)) as char`で実施できるので、それをうまく使います。
今回の入力は0の場合は特殊なのと、アルファベットに変換するときは1-Indexedなので注意

### 解答

https://atcoder.jp/contests/abc294/submissions/39846218

```Rust
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        h:usize,
        w:usize,
        a:[[u8;w];h],
    }
    for a in a {
        println!(
            "{}",
            a.into_iter()
                .map(|i| if i == 0 { '.' } else { (b'A' + i - 1) as char })
                .collect::<String>()
        )
    }
}
```

## [問題C](https://atcoder.jp/contests/abc294/tasks/abc294_c)

### 考察

aとbをまとめた配列cを作成して、ソートし、`HashMap`などで

- Key 数字
- Value 配列cで何番目か

を管理すればあとはaとbそれぞれについてMapを参照すれば解答できます。

### 解答

https://atcoder.jp/contests/abc294/submissions/39891929

```Rust
use std::collections::HashMap;

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

fn main() {
    input! {
        n:usize,
        m:usize,
        a:[usize;n],
        b:[usize;m],
    }
    let mut c = a.iter().chain(b.iter()).collect::<Vec<_>>();
    c.sort();

    let mut map = HashMap::new();
    for i in 0..n + m {
        map.insert(c[i], i + 1);
    }

    println!("{}", a.iter().map(|i| map[&i]).join(" "));
    println!("{}", b.iter().map(|i| map[&i]).join(" "));
}
```

## [問題D](https://atcoder.jp/contests/abc294/tasks/abc294_d)

### 考察

自分は`BTreeSet`で最小の要素の取得と、任意の要素の削除が高速にできるのでそちらで実装しました。
次呼ばれる人を`next`という変数で受けて、呼ばれたが受付に行っていない人を`set`で管理しています。

### 解答

https://atcoder.jp/contests/abc294/submissions/39892034

```Rust
use std::collections::BTreeSet;

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        _:usize,
        q:usize,
    }
    let mut next = 1;
    let mut set = BTreeSet::new();
    for _ in 0..q {
        input! {qi: u8}
        if qi == 1 {
            set.insert(next);
            next += 1;
        } else if qi == 2 {
            input! {x:usize}
            set.remove(&x);
        } else {
            println!("{}", set.iter().next().unwrap());
        }
    }
}
```

## [問題E](https://atcoder.jp/contests/abc294/tasks/abc294_e)

### 考察

コンテスト中は`vl1`と`vl2`をマージしたような配列`vl`を作成し、
`vl1`の値を足しつつ`vl2`の値を引いて、0のものを足し合わせると実装したのですが、

実装も少し大変だったので、シンプルに配列に対して操作しつつ前から足し合わせるのがよさそうです。

### 解答

https://atcoder.jp/contests/abc294/submissions/39892467

```Rust
use proconio::input;

fn main() {
    input! {
        _:usize,
        n1:usize,
        n2:usize,
        mut vl1:[(i64,usize);n1],
        mut vl2:[(i64,usize);n2],
    }
    let mut i1 = 0;
    let mut i2 = 0;
    let mut ans = 0;
    while i1 != n1 && i2 != n2 {
        let seg = vl1[i1].1.min(vl2[i2].1);
        if vl1[i1].0 == vl2[i2].0 {
            ans += seg;
        }
        vl1[i1].1 -= seg;
        vl2[i2].1 -= seg;
        if vl1[i1].1 == 0 {
            i1 += 1;
        }
        if vl2[i2].1 == 0 {
            i2 += 1;
        }
    }
    println!("{}", ans);
}
```

## [問題F](https://atcoder.jp/contests/abc294/tasks/abc294_f)

### 考察

二分探索で解くのですが、そのときに特定の濃度$K$以上かどうかを判定するために、濃度が`K`になるためには砂糖がどれだけ過不足しているか、を青木くんか高橋くんのどちらかについてあらかじめ計算してソートおくと、`lower_bound`などの二分探索を用いて判定が$O(N)$か$O(M)$で行えます。
`superSlice`の`lower_bound`は`f64`に対しては使えないので、自前で実装しています。

### 解答

```Rust
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n:usize,
        m:usize,
        k:Usize1,
        ab:[(usize,usize);n],
        cd:[(usize,usize);m],
    }
    let mut lower = 0.0;
    let mut upper = 100.0;
    while upper - lower > 1e-10 {
        let med = (lower + upper) / 2.0;
        if is_over_k(&ab, &cd, med, k) {
            lower = med;
        } else {
            upper = med;
        }
    }
    println!("{}", upper);
}

fn is_over_k(ab: &Vec<(usize, usize)>, cd: &Vec<(usize, usize)>, med: f64, k: usize) -> bool {
    let mut sug = vec![];
    for &(a, b) in ab {
        sug.push((a + b) as f64 * med / 100.0 - a as f64);
    }
    sug.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let mut count = 0;
    for &(c, d) in cd {
        let su = (c + d) as f64 * med / 100.0 - c as f64;
        count += lower_bound(&sug, -su);
    }
    k < count
}

fn lower_bound(v: &Vec<f64>, t: f64) -> usize {
    let mut lower = 0;
    let mut upper = v.len();
    while upper != lower {
        let med = (lower + upper) / 2;
        if v[med] < t {
            lower = med + 1;
        } else {
            upper = med;
        }
    }
    lower
}
```

## [問題G](https://atcoder.jp/contests/abc294/tasks/abc294_g)

### 考察

`dfs`で各辺が何番目に通ったかと、各頂点を何番目に通ったかを記録しつつ、Fenwick Treeで行きのときにコストを足して、帰りのときにコストを引いて記録します。
あとは、クエリごとにFenwick Treeを更新したり、LCAを用いてコストを求めたりして実装できます。

### 解答

長いので、ライブラリ部分は省略

https://atcoder.jp/contests/abc294/submissions/39885254

```Rust
use proconio::{fastout, input, marker::Usize1};

#[fastout]
fn main() {
    input! {
        n:usize,
        mut uvw:[(Usize1,Usize1,i64);n-1],
        q:usize,
    }
    let mut edges = vec![vec![]; n];
    for i in 0..n - 1 {
        edges[uvw[i].0].push(uvw[i].1);
        edges[uvw[i].1].push(uvw[i].0);
    }
    let mut lca = LCA::new(n);
    lca.init(&edges, 0);

    let mut g = vec![vec![]; n];
    for i in 0..n - 1 {
        g[uvw[i].0].push((uvw[i].1, uvw[i].2, i));
        g[uvw[i].1].push((uvw[i].0, uvw[i].2, i));
    }
    let mut fw = FenwickTree::new(2 * n + 2);

    let mut vertex = vec![0; n];
    let mut edges = vec![(0, 0); n];
    dfs(0, 0, 1, &mut fw, &g, &mut vertex, &mut edges);

    for _ in 0..q {
        input! {q: u8}
        if q == 1 {
            input! {i: Usize1, w :i64}
            fw.add(edges[i].0, -uvw[i].2 + w);
            fw.add(edges[i].1, uvw[i].2 - w);
            uvw[i].2 = w;
        } else {
            input! {u:Usize1,v:Usize1}
            let l = lca.query(u, v);
            println!(
                "{}",
                fw.sum(vertex[u]) + fw.sum(vertex[v]) - 2 * fw.sum(vertex[l])
            )
        }
    }
}

fn dfs(
    cur: usize,
    prev: usize,
    mut idx: usize,
    fw: &mut FenwickTree,
    g: &Vec<Vec<(usize, i64, usize)>>,
    vertex: &mut Vec<usize>,
    edges: &mut Vec<(usize, usize)>,
) -> usize {
    for &(next, cost, i) in &g[cur] {
        if next == prev {
            continue;
        }
        fw.add(idx, cost);
        edges[i].0 = idx;
        vertex[next] = idx;
        idx = dfs(next, cur, idx + 1, fw, g, vertex, edges);
        idx += 1;
        fw.add(idx, -cost);
        edges[i].1 = idx;
    }
    idx
}
```