Magicode logo
Magicode
0

RustとAtCoderを勉強する(typical90_g)

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。

今回は、競プロ典型90問007 - CP Classes(★3)を解きました。

提出コード


解説

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


同じ値が見つかると Ok(i) として、同じ値が見つからなかった場合は Err(i) として、要素が挿入される場所を返します。また、Vec のどの値よりも大きかった場合は添字の範囲外となる Vec::len() がが返ってくることに注意してください。さらに、同じ値が複数ある場合はそのうちのどれかの添字が返ります。これを踏まえて、以下のように binary_search() の戻り値に対して match 式で場合分けを行いました。


  • Ok(_) => 0

Ok が返ってくる時は b と全く同じレートの教室があるということを意味しているため、その差は常に 0 となります。

  • Err(0) => a[0] - b

Err(0) の時、ba[0] より確実に小さい値となります。

  • Err(x) if x == a.len() => b - a[x - 1]

Err(x) if x == a.len() となるのは ba のどの値よりも大きい場合です。

  • Err(x)

上のどのパターンでもない場合にマッチします。

まとめ

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

Discussion

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