👨‍🍳

ABC388:Rustで解く!問題解説

2025/01/12に公開

AtCoder Beginner Contest 388のA~E問題をRustで解いた際の解法をまとめました。

A問題

  • 問題

https://atcoder.jp/contests/abc388/tasks/abc388_a

  • 解説

SUPC を付け加えた文字列を出力します。

  • コード
use proconio::{input, marker::Chars};
fn main() {
    input!{
        s: Chars,
    }
    println!("{}UPC", s[0]);
}

B問題

  • 問題

https://atcoder.jp/contests/abc388/tasks/abc388_b

  • 解説

ヘビの重さは、太さ × (元々の長さ + 伸びた長さ k ) で求められます。
ここで k はヘビの長さがどれだけ伸びたかを示します。
k だけ長さが伸びた状態での各ヘビの重さを計算し、その最大値を求めます。
この計算を k=1 から D まで順番に行います。

  • コード
use proconio::input;
use std::cmp::max;
fn main() {
    input!{
        n: usize, d: usize,
        tl: [(usize, usize); n],
    }
    for k in 1..=d {
        let mut ans = 0;
        for &(t, l) in &tl {
            ans = max(t * (l+k), ans);
        }
        println!("{}", ans);
    }
}

C問題

  • 問題

https://atcoder.jp/contests/abc388/tasks/abc388_c

  • 解説

餅を2つ選んだときの小さい方を a 、大きい方を b とし、この2つを全探索すると、
O(N^2) の計算量となり、実行時間を超過してしまうため解くことができません。
そこで探索方法を工夫します。
b を全探索し、①「 b / 2 の半分以下の a の個数」を計上していきます。
①を満たす個数は二分探索を使うことで O(\log{N}) で求められるため、
全体の時間計算量は O(N \log{N}) となり、実行時間内に解くことができます。

  • コード
use proconio::input;
const INF: usize = 1 << 60;

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

    let mut ans = 0;

    // aの各要素に対して処理を行う
    for i in 0..n {
        let val = a[i] / 2; // bの半分
        let pos = below_bound(&a, val); // b / 2以下のaの個数をカウント
        if pos == INF { continue; } // 異常値の場合はスキップ
        ans += pos + 1; // 個数を加算
    }
    println!("{}", ans);
}

// 二分探索
// x以下の最大のposを返す。0番目より小さい値では異常値として、「1<<60」を返す
pub fn below_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize {
    let mut l = 0;
    let mut r = vec.len();
    while r - l > 0 {
        let m = (l + r) / 2;
        if vec[m] <= val {
            l = m + 1; // val以下の値を探す
        } else {
            r = m; // valより大きい値を探す
        }
    }
    if l == 0 { INF } else { l - 1 } // 異常値の処理
}

D問題

  • 問題

https://atcoder.jp/contests/abc388/tasks/abc388_d

  • 解説

N 人の宇宙人が石を配る動作を N 年分そのまま試すと、
O(N^2) の計算量となり、実行時間を超過してしまうためそのままでは解くことができません。

N年後の石の個数を求めればよいので、石の増減に注目し以下のように問題を読み替えます。

i 番目の宇宙人は、①「前にいる何人から合計 x 個の石をもらい」、
②「連続する後ろの人全員(渡すことができる人数)分の合計 y 個の石を渡す」。

よって、①による石の増加、②による石の減少をまとめて行うことができます。

ここで②による石の配り方ですが、imos法の考え方を用いて石の増減が生じる境界部分に注目します。
開始位置(A)を +1 、終了位置(B)を -1 し、累積和を計算して範囲内を更新します。
累積和は各人について1度ずつ行う必要があるので、
①で石を受け取ったタイミングでその加算分を隣に伝播させる必要があります。

  • コード
use proconio::input;
use std::cmp::min;
use itertools::Itertools;

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

    let mut add_array = vec![0i64; n+1];

    for i in 0..n {
        // 受け取り分取得
        let get_val = add_array[i];
        a[i] += get_val;

        // 受け取り値を隣に伝播
        add_array[i + 1] += get_val;

        // 配れる人数yを決めて、配る
        let y = min(a[i], (n - 1 - i) as i64);
        a[i] -= y;

        // 今の位置から、y人それぞれ+1
        // imos法で開始と終了後だけを更新
        add_array[i + 1] += 1;
        add_array[i + (y + 1) as usize] -= 1;
    }
    println!("{}", a.iter().join(" "));
}

E問題

  • 問題

https://atcoder.jp/contests/abc388/tasks/abc388_e

  • 解説

N 個の餅を2つ選んでペアにするため、ペア数の最大値は\lfloor N / 2 \rfloorとなります。
そのため、まず①「大きいN / 2個」と、②「小さいN / 2個」のグループに分けます。
①、②のグループの要素を優先度付きキューにそれぞれ追加し、キューの先頭の要素を比較してペアにしていきます。

  • ①の先頭の値 >= ②の先頭の値 * 2
    ペアにできるので、両方取り出してペア数を +1 します。

  • ①の先頭の値 < ②の先頭の値 * 2
    ②で取り出した値をペアにする方法がないので、②の要素だけを取り出します。

  • コード

use proconio::input;
use std::collections::BinaryHeap;

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

    // aを半分ずつに分ける (奇数の場合、中央値を捨てる)
    let mut small_hp = BinaryHeap::new(); // 小さい方の要素を格納するキュー
    let mut large_hp = BinaryHeap::new(); // 大きい方の要素を格納するキュー

    for i in 0..n/2 {
        small_hp.push(a[i]); // 小さい方の要素を追加
        large_hp.push(a[n-1-i]); // 大きい方の要素を追加
    }

    let mut ans = 0; // ペア数をカウントする変数
    for _i in 0..n/2 {
        // small_hpが空の場合はスキップ
        if small_hp.len() == 0 { continue; }

        // 大きい方から見てマッチングさせる
        if large_hp.len() != 0 { 
            let large = *large_hp.peek().unwrap(); // 大きい方の先頭の値を取得
            let small = *small_hp.peek().unwrap(); // 小さい方の先頭の値を取得
            
            // 組み合わせられる場合
            if small * 2 <= large {
                ans += 1; // ペア数を+1
                large_hp.pop().unwrap(); // 大きい方の要素を取り出す
                small_hp.pop().unwrap(); // 小さい方の要素を取り出す
            }
            // 組み合わせられない場合
            else {
                small_hp.pop().unwrap(); // 小さい方の要素を取り出す
            }
        }
    }
    println!("{}", ans); // 結果を出力
}

Discussion