AtCoder Beginner Contest 434のA～E問題を緑コーダーが自分なりの解説と解答コードをまとめました。
参考になりましたら幸いです。

ABC434-A

問題

体重 $W \text{ [kg]}$ の人が、風船 $1$ 個あたりの重さ $B \text{ [g]}$ の風船を何個持てば、
風船の総重量が体重を上回るかを求める問題です。

解説

体重 $W \text{ [kg]}$ をグラムに変換し、風船 $1$ 個の重さ $B \text{ [g]}$
で割った商に $1$ を加えることで、必要な風船の個数を求めることができます。
具体的には、 $(W \times 1000 / B) + 1$ で求めることができます。

コード

abc434a.rs

use proconio::input;

fn main() {
    input! {
        w: usize, // 体重[kg]
        b: usize, // 風船の1個あたりの重量[g]
    }

    // 風船の個数をxとして、体重 < x * bを満たすxを求める。
    let x = (w * 1000 / b) + 1;
    println!("{}", x);
}

ABC434-B

問題

$N$ 匹の鳥について、種類ごとの大きさの平均を求める問題です。

解説

鳥の種類ごとに大きさを合計し、その種類に属する鳥の数で割ることで平均値を求めることができます。
割り算を行う際、結果が小数になる可能性があるため、浮動小数点数として計算する必要がある点に注意します。

コード

abc434b.rs

use proconio::input;

fn main() {
    input! {
        n: usize, // 鳥の匹数
        m: usize, // 鳥の種類
        ab: [(usize, usize); n], // 各鳥(種類と大きさ)
    }

    // 種類毎の大きさの平均値を求める
    let average = calc_average(n, m, &ab);
    for i in 1..=m {
        println!("{}", average[i]);
    }
}

fn calc_average(_n: usize, m: usize, ab: &Vec<(usize, usize)>) -> Vec<f64> {
    // 種類毎の個数と大きさの総和を求める
    let mut cnt = vec![0; m+1];
    let mut total = vec![0; m+1];
    for &(kind, tall) in ab {
        cnt[kind] += 1;
        total[kind] += tall;
    }

    // 種類毎の平均を求める
    let mut average = vec![0.0; m+1];
    for i in 1..=m {
        average[i] = total[i] as f64 / cnt[i] as f64;
    }
    average
}

ABC434-C

問題

高度 $H$ の状態から高さを変えながら移動する際に、全ての中継地点に到達できるかを判定する問題です。

解説

動的に変化する現在の到達可能高度の範囲を管理することで解くことができます。

各中継地点には、到達するための条件として「時刻」「高度の下限」「高度の上限」が与えられます。現在の高度の範囲を考慮しながら、次の中継地点に到達可能かを判定します。

現在の高度範囲を $[l, r]$ とし、次の中継地点に到達するまでの時間を $d$ とします。

高度の範囲は、時間 $d$ に応じて $[l-d, r+d]$ に広がります。
次の中継地点の高度条件 $[l_{next}, r_{next}]$ と比較し、交差する部分があるかを確認します。
- 交差する部分がない場合、到達は不可能です。
- 交差する部分がある場合、その範囲に高度を収めるように更新します。

全ての中継地点で条件を満たせば Yes を出力し、1つでも満たせない場合は No を出力します。

コード

abc4334c.rs

use proconio::input;
use std::cmp::{min, max};

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct Range {
    l: i64,
    r: i64,
}
fn main() {
    input! {
        t: usize, // テストケース数
    }
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    input! {
        n: usize, // 中継地点の数
        h: i64, // 初めの高度
        tlu: [(i64, i64, i64); n], // 中継点毎の条件(時刻、高度のmin,高度のmax)
    }

    // 現在の高度(min,max)と現在時刻
    let mut cur_h = Range {l: h, r: h};
    let mut cur_time = 0;

    // 各中継地点に順番に移動
    for (next_time, next_l, next_r) in tlu {
        // 変化時間
        let d = next_time - cur_time;
        
        // 中継地点の条件を満たせるかを判定
        if cur_h.r + d < next_l || next_r < cur_h.l - d {
            println!("No");
            return;
        }
        
        // 高度,時刻の更新
        cur_h.l = max(cur_h.l - d, next_l);
        cur_h.r = min(cur_h.r + d, next_r);
        cur_time = next_time;
    }
    
    // 全て条件を満たした
    println!("Yes");
}

ABC434-D

問題

$N$ 個の雲が配置された空のマス全体から、特定の1つの雲のみを取り除いたとき、雲がないマスの総数を答える問題です。

解説

二次元いもす法を用いて解くことができます。
まず、特定の雲 $i$ を取り除いたときの雲がないマスの総数 $A_i$ は、以下の式で求められます。

A_i = (\text{空全体のマス数}) - (\text{雲が1つ以上あるマスの総数}) + (\text{雲}i\text{のみ存在するマスの総数})

空全体のマス数
空マスの範囲は、縦と横が2000ずつと決まっているため、 $2000 \times 2000$ です。
雲が1つ以上あるマスの総数
各マスについて、雲の個数が1個以上であるかどうかを数えます。
これは、すべての雲について $+1$ の値を設定した二次元いもす配列を作成し、
その累積和を取ることで、各マスに存在する雲の個数を求めることで達成できます。
その後、個数が1以上のマスの数を数えればよいです。
雲 $i$ のみ存在するマスの総数
雲の個数がちょうど1個であり、かつそれが雲 $i$ であるマスの総数を数えます。
これも二次元いもす法で求めます。
ただし、雲 $i$ には $+i$ （ $i$ は1-indexed）の重みを設定します。
雲の個数がちょうど1個であるマスについて、そのマスの重みが $i$ であれば、
そのマスは雲 $i$ のみが存在するマスだと分かります。

これらの値を求めることで、上記の式に基づき、各雲 $i$ を取り除いた場合の雲がないマスの総数を効率的に計算できます。

コード

abc434d.rs

use proconio::input;
const SZ: usize = 2000;
fn main() {
    input! {
        n: usize, // 雲の数
        udlr: [(usize, usize, usize, usize); n], // 雲の範囲(上下、左右)
    }

    // 二次元いもす法で、雲の個数を求める
    let mut imos2d_cnt = calc_imos2d_cnt(n, &udlr);
    // 二次元いもす法で、雲iの重みを求める(iは1-indexed)
    let mut imos2d_weight = calc_imos2d_weight(n, &udlr);
    
    // 二次元いもす法のグリッド範囲を取得
    let grid_sz = imos2d_cnt.sz;
    
    // 全体のマス
    let total_grid = (SZ * SZ) as i64;
    // 雲が1個以上あるマスの総数
    let total_cloud = calc_total_cloud(grid_sz, &mut imos2d_cnt);
    // 雲の個数が1個のマスについて、種類毎に数える
    let cloud_cnt = count_cloud(n, grid_sz, &mut imos2d_cnt, &mut imos2d_weight);

    // 雲iを削除した時の雲がないマスを答える
    for idx in 1..=n {
        // 全体のマス - 雲が1個以上あるマスの総数 + 雲iのみマスの総数
        println!("{}", total_grid - total_cloud + cloud_cnt[idx]);
    }
}

fn calc_imos2d_cnt(n: usize, udlr: &Vec<(usize, usize, usize, usize)>) -> Imos2D{
    let mut ret = Imos2D::new(SZ+1);
    for i in 0..n {
        let (u, d, l, r) = udlr[i];
        ret.set_range_2d(u, d, l, r, 1);
    }
    ret.exec_add_range();
    ret
}

fn calc_imos2d_weight(n: usize, udlr: &Vec<(usize, usize, usize, usize)>) -> Imos2D{
    let mut ret = Imos2D::new(SZ+1);
    for i in 0..n {
        let (u, d, l, r) = udlr[i];
        ret.set_range_2d(u, d, l, r, (i+1) as i64);
    }
    ret.exec_add_range();
    ret
}

fn calc_total_cloud(sz: usize, imos2d_cnt: &mut Imos2D) -> i64 {
    let mut ret = 0;
    for i in 0..sz {
        for j in 0..sz {
            if imos2d_cnt.grid[i][j] >= 1 {
                ret += 1;
            }
        }
    }
    ret
}

fn count_cloud(n: usize, sz: usize, imos2d_cnt: &mut Imos2D, imos2d_weight: &mut Imos2D) -> Vec<i64> {
    let mut ret = vec![0; n+1];
    for i in 0..sz {
        for j in 0..sz {
            if imos2d_cnt.grid[i][j] == 1 {
                let idx = imos2d_weight.grid[i][j] as usize;
                ret[idx] += 1;
            }
        }
    }
    ret
}

struct Imos2D {
    sz: usize,
    grid: Vec<Vec<i64>>,
}
impl Imos2D {
    // 初期化
    pub fn new(sz: usize) -> Self {
        let grid = vec![vec![0; sz+2]; sz+2];
        Imos2D { sz, grid }
    }
    // 区間加算する範囲のセット [top..bottom] [left..right]
    pub fn set_range_2d(&mut self, top: usize, bottom: usize, left: usize, right: usize, val: i64){
        self.grid[top][left] += val;
        self.grid[top][right+1] -= val;
        self.grid[bottom+1][left] -= val;
        self.grid[bottom+1][right+1] += val;
    }
    // 加算の実行
    pub fn exec_add_range(&mut self) {
        // 横方向の加算
        for i in 0..self.sz {
            for j in 0..self.sz {
                self.grid[i][j+1] += self.grid[i][j];
            }
        }
        // 縦方向の加算
        for i in 0..self.sz {
            for j in 0..self.sz {
                self.grid[i+1][j] += self.grid[i][j];
            }
        }
    }
}

ABC434-E

問題

$N$ 匹のウサギについて、ジャンプ後の座標の種類数の最大値を求める問題です。

解説

ジャンプ後の座標を頂点、ウサギのジャンプを辺と見なしてグラフを構成し、その連結成分をUnion-Findで処理することで解くことができます。

まず、ウサギのジャンプ後の座標の値が大きいため、これらの座標を一旦集めて座標圧縮し、小さい整数インデックスに置き換えます。そのうえで、座標圧縮した座標を用いてグラフ構築をします。

各ウサギ $i$ は、左に $r_i$ ジャンプした座標 $x_i - r_i$ と、右に $r_i$ ジャンプした座標 $x_i + r_i$ に移動できます。
この $x_i - r_i$ と $x_i + r_i$ を頂点と見なし、ウサギ $i$ のジャンプによってこれら2つの頂点間に辺があると考えます。
全てのウサギのジャンプに対応する辺について、Union-Findで2つの座標（頂点）を併合（merge）します。これにより、到達可能な座標のグループ、すなわち連結成分が求まります。
その後、連結成分ごとに、到達可能な座標の種類の最大数を求めます。
連結成分内の頂点数を $V$ （座標の種類数）、辺の数を $E$ （ウサギの数）として数え上げる際は、連結成分が閉路なし、閉路ありに以下場合分けして数えます。

閉路なしの場合
- ジャンプ先として選べる座標の種類数は $E$ となります。
閉路ありの場合
- 最大で $V$ 種類の異なる座標に到達できます。

全ての連結成分について求めた $V$ または、 $E$ による総和が、答えとなります。

コード

abc434e.rs

use proconio::input;
use std::cmp::min;
use std::collections::{BTreeSet, BTreeMap};
use std::mem::swap;

fn main() {
    input!  {
        n: usize, // ウサギの引数
        xr: [(i64, i64); n], // ウサギの座標とジャンプ移動する距離
    }

    // 各ウサギについて、ジャンプ後の座標集合を記録
    let st_pos = get_pos_set(&xr);
    
    // 座標圧縮を実施
    let mut comp = Compressor::new(&st_pos);
    
    // UnionFindの初期化
    let mut uf = UnionFind::new(comp.sz);
    // 辺の連結
    join_uf(&mut uf, &xr, &mut comp);
    // 連結成分毎の辺の本数を求める
    let group_edge = count_group_edge(&mut uf, &xr, &mut comp);

    // 連結成分毎に座標数をカウント
    let mut ans = 0;
    for i in 0..comp.sz {
        // 親の連携成分のサイズと辺の本数のうち、小さい方を加算
        if uf.find(i) != i { continue; }
        ans += min(uf.get_group_size(i), group_edge[i]);
    }
    println!("{}", ans);
}

fn get_pos_set(xr: &Vec<(i64, i64)>) -> BTreeSet<i64>{
    let mut st_pos = BTreeSet::new();
    for &(x, r) in xr {
        st_pos.insert(x - r);
        st_pos.insert(x + r);
    }
    st_pos
}

fn join_uf(uf: &mut UnionFind, xr: &Vec<(i64, i64)>, comp: &mut Compressor) {
    // 左方向に飛んだ場合と右方向に飛んだ場合を辺とみなして、辺を連結
    for &(x, r) in xr {
        let left = comp.get_idx_bykey(x - r);
        let right = comp.get_idx_bykey(x + r);
        uf.merge(left, right);
    }
}

fn count_group_edge(uf: &mut UnionFind, xr: &Vec<(i64, i64)>, comp: &mut Compressor) -> Vec<usize>{
    let mut group_edge = vec![0; comp.sz];
    for &(x, r) in xr {
        let left = comp.get_idx_bykey(x - r);
        group_edge[uf.find(left)] += 1;
    }
    group_edge
}

// 座標圧縮
#[allow(unused)]
struct Compressor {
    bmp: BTreeMap<i64, usize>,    // bmp[key] = idx
    vec: Vec<i64>,                // vec[idx] = key
    sz: usize
}
impl Compressor {
    // 初期化
    pub fn new(bset: &BTreeSet<i64>) -> Self {
        let mut bmp = BTreeMap::new();
        let mut vec = Vec::new();
        let mut sz = 0;
        for &item in bset {
            bmp.insert(item, sz);
            vec.push(item);
            sz += 1;
        }
        Compressor { bmp, vec, sz}
    }

    #[allow(unused)]
    pub fn get_idx_bykey(&mut self, key: i64) -> usize {
        match self.bmp.get(&key) {
            Some(&idx) => idx,
            None => INVALID_VALUE,
        }
    }
}
// 値が見つからなかったとき用の値
const INVALID_VALUE: usize = 1 << 60;

// Union-Find構造体
#[allow(unused)]
struct UnionFind {
    verb: usize, // 頂点数
    g_size: Vec<usize>,  // 各頂点の集合サイズ
    g_parent: Vec<isize>,      // 親情報
}

impl UnionFind {
    // 初期化
    fn new(n: usize) -> Self {
        UnionFind { verb: n, g_size: vec![1; n], g_parent: vec![-1; n] }
    }

    // 代表元を求める
    fn find(&mut self, u: usize) -> usize {
        if self.g_parent[u] == -1 {
            return u;
        }
        let p = self.g_parent[u] as usize;
        let root = self.find(p);
        // 経路圧縮
        self.g_parent[u] = root as isize;
        root
    }

    // 2つの集合を併合
    fn merge(&mut self, u: usize, v: usize) -> bool {
        let mut x = self.find(u);
        let mut y = self.find(v);
        if x == y {
            // 既に同じ集合
            return false; 
        }
        if self.g_size[x] < self.g_size[y] {
            swap(&mut x, &mut y);
        }
        self.g_parent[y] = x as isize;
        self.g_size[x] += self.g_size[y];
        true
    }

    // 同じ集合かどうかを判定
    #[allow(unused)]
    fn is_same(&mut self, u: usize, v: usize) -> bool {
        self.find(u) == self.find(v)
    }

    #[allow(unused)]
    // 集合のサイズを取得
    fn get_group_size(&mut self, u: usize) -> usize {
        let root = self.find(u);
        self.g_size[root]
    }
}

Discussion