Ccmmutty logo
Commutty IT
・3 min read

RustとAtCoderを勉強する(typical90_g)

AtCoderRust
https://cdn.magicode.io/media/notebox/blob_hBCqb2N

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の007 - CP Classes（★3）を解きました。

提出コード

rust
use proconio::input;

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

    a.sort_unstable();
    a.dedup();
    for b in b {
        let complain = match a.binary_search(&b) {
            Ok(_) => 0,
            Err(0) => a[0] - b,
            Err(x) if x == a.len() => b - a[x - 1],
            Err(x) => (a[x] - b).min(b - a[x - 1]),
        };
        println!("{}", complain);
    }
}

解説

N 個の教室から自分と一番実力の近い教室を探し、その教室の対象レートと自分のレートの差を求める問題です。今回の問題では教室・生徒ともに最大 300000 なので、全生徒で全教室を全探索すると時間切れとなります。そのため、教室を対象レートでソートした後に、生徒のレートと一番近い教室を二分探索します。rust では、Vec 型に binary_search() メソッドが実装されています。binary_search() の使用例は以下のプログラムの通りです。
rust
let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];

assert_eq!(s.binary_search(&13),  Ok(9));
assert_eq!(s.binary_search(&4),   Err(7));
assert_eq!(s.binary_search(&100), Err(13));
let r = s.binary_search(&1);
assert!(match r { Ok(1..=4) => true, _ => false, });
同じ値が見つかると Ok(i) として、同じ値が見つからなかった場合は Err(i) として、要素が挿入される場所を返します。また、Vec のどの値よりも大きかった場合は添字の範囲外となる Vec::len() がが返ってくることに注意してください。さらに、同じ値が複数ある場合はそのうちのどれかの添字が返ります。これを踏まえて、以下のように binary_search() の戻り値に対して match 式で場合分けを行いました。
rust
let complain = match a.binary_search(&b) {
    Ok(_) => 0,
    Err(0) => a[0] - b,
    Err(x) if x == a.len() => b - a[x - 1],
    Err(x) => (a[x] - b).min(b - a[x - 1]),
};
  • Ok(_) => 0 Ok が返ってくる時は b と全く同じレートの教室があるということを意味しているため、その差は常に 0 となります。
  • Err(0) => a[0] - b Err(0) の時、b は a[0] より確実に小さい値となります。
  • Err(x) if x == a.len() => b - a[x - 1] Err(x) if x == a.len() となるのは b が a のどの値よりも大きい場合です。
  • Err(x) 上のどのパターンでもない場合にマッチします。

まとめ

rust で二分探索を行いました。少し match 式で場合分けを行うのが面倒な気もしますが、結果をそのまま変数に代入できるのはいいと思います。

Discussion

コメントにはログインが必要です。