競プロ典型90問をRustで解いていこう（貪欲法）11日目
はじめに
実家においてきた本を整理してきました。 ダンボール30箱ぐらいに詰め込んで不要な（苦渋の決断で手放した本も含む）本達を売りにだしたわけです。 これだけ本があると中には、絶版になって高値になっている本も数冊でてくるもんだと驚いてます。 特に驚いたのはこいつですね。
当時Amazonで購入した値段が54円だったのですが、7500円前後で取引されているらしく驚いています。 シリーズものなので、全部そろえておけよって気持ちになりましたがこの一冊だけでした。 個人経営の古本屋とか漁ればもしかしたら800円ぐらいで売られてんじゃないかと思わなくもないですが…あらぁって値段がついてます。
同じ作者の本で、こちらもありました。 こちらは当時、700円でしたが何が価値を持つのかわからんもんですね。
今になって読み返すとたしかに必要だったものが書かれているような気がしてます。 一瞬、ここまで値段上がってるのならメルカリに出そうかと思いましたが、自分で使ってからでもいいかなとなりました。
結果として1500冊近く売りに出したりしてきたわけですが、その中で1000円以上の値段がつきそうな本は30冊。 プレミアがついて、5000円以上になりそうな本は上の本を入れても5冊程度と非常に芳しくありません。
殆ど読まずに手放すことになった本ばかりで、金を溝に捨てたような気持ちなのです。 ものが減ってスッキリするというのは持ち主でない人の感想であって、捨てる本人からするとなんとも言えない気持ちになります。
さて、気を取り直してやっていきましょう。
014 We Used to Sing a Song Together（★3）
生徒がＮ人いて、みんな仲が悪いので別々の学校に通いたいと考えています。 学校も人数分だけあり、生徒の家の位置と学校の位置が与えられるので、 それぞれの生徒が通う距離の合計を最小にするという問題です。
近隣住人の関係性が限界ではありますが解いていきます。
方針としては、学校の位置と家の位置のリストを並び替えてから、 近しいところから順番に選び取っていくやり方で解いてみます。いわゆる貪欲法と呼ばれる手法です。
貪欲法というのは、大きな問題があってそれを達成するために問題を細分化して その各問題で最適となるような選び方をすれば大きな問題も最適な解となるんじゃね？って選び方です。
実装
Rustでこんな感じに書いてみました。どうでしょうか。
use proconio::input;
use std::vec::Vec;
fn main() {
input! {
n : usize,
mut a : [i128;n],
mut b : [i128;n]
}
a.sort();
b.sort();
let mut ans = 0;
for i in 0..n {
let v = a[i] - b[i];
ans += v.abs();
}
println!("{:?}", ans);
}
実行結果
通りましたね。
まとめ
何が価値を持つのかわからないもんです。 オタクあるあるなんでしょうが、専門書とかに限らず欲しいものを買うことに躊躇っていると、 信じられないぐらい値段が跳ね上がって購入できなくなる経験を何度もしてきたので、貪欲法のように局所最適を目指すため 欲しいものはすぐに買うことを心がけたいものですね。
これとかも当時2000円ぐらいで購入でたのに、ホント惜しいことをしたと嘆いています。ほんとにこれは欲しい。 Steamで購入できるんだけどＰＳでやりたい。 ゲームのシナリオが映画の脚本家が作っているようで、中身は実質バック・トゥ・ザ・フューチャー4なんですよ。マジ。 映画の続編なんですけどね、名作なんですよ。それをPSで出たときに買っておくべきだったんですよ。ほんとに…悔やまれる…
何はともあれ、簡単な実装で求める解が得られるのはいいですねシンプルです。
amazon.co.jp
