・0 pv・3 min read
RustとAtCoderを勉強する(typical90_g)
はじめに
AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の007 - CP Classes（★3）を解きました。
提出コード
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() の使用例は以下のプログラムの通りです。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 式で場合分けを行いました。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(_) => 0Okが返ってくる時はbと全く同じレートの教室があるということを意味しているため、その差は常に 0 となります。 -
Err(0) => a[0] - bErr(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 式で場合分けを行うのが面倒な気もしますが、結果をそのまま変数に代入できるのはいいと思います。