RustでAtcoder Beginner Contest100のD問題を解いた::8/20
高橋君はプロのパティシエになり, AtCoder Beginner Contest 100 を記念して, 「ABC洋菓子店」というお店を開いた.
ABC洋菓子店では, $N$ 種類のケーキを売っている.各種類のケーキには「綺麗さ」「おいしさ」「人気度」の $3$つの値を持ち, $i$種類目のケーキの綺麗さ$x_i$は, おいしさは$y_i$, 人気度$z_i$は である.これらの値は$0$以下である可能性もある. りんごさんは, ABC洋菓子店で$M$個のケーキを食べることにした. 彼は次のように, 食べるケーキの組み合わせを選ぶことにした.
- 同じ種類のケーキを $2$個以上食べない.
- 上の条件を満たしつつ, (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ.
このとき, りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を求めなさい.
色々と格闘した結果書けたけどこれでいいのか~という気持ちになってる
こんな書き方でいいのか強い方に見てほしいという気持ちになっている.
D問題
use std::cmp::max; use std::fmt::Debug; use std::io::stdin; use std::str::FromStr; fn read<T>() -> Vec<T> where T: FromStr, <T as FromStr>::Err: Debug, { let mut s = String::new(); stdin().read_line(&mut s).unwrap(); s.trim() .split_whitespace() .map(|c| T::from_str(c).unwrap()) .collect() } #[derive(Clone)] struct Review { x: i64, y: i64, z: i64, } impl Review { fn new(r: &[i64]) -> Review { Review { x: r[0], y: r[1], z: r[2], } } fn dot(&self, o: &Review) -> i64 { o.x * self.x + o.y * self.y + o.z * self.z } } fn main() { let x: Vec<usize> = read(); let mut select: Vec<Review> = Vec::new(); for i in 0..8 { let v: Vec<i64> = vec![i & 0x4, i & 0x2, i & 0x1] .iter() .map(|&i| if i == 0 { -1 } else { 1 }) .collect(); select.push(Review::new(v.as_slice())); } let mut reviews: Vec<Review> = Vec::new(); for _ in 0..x[0] { let r: Vec<i64> = read(); reviews.push(Review::new(r.as_slice())); } println!( "{}", select .iter() .map(|sel| { let mut biased_points: Vec<i64> = reviews.iter() .map(|v| v.dot(&sel)) .collect::<Vec<i64>>(); biased_points.sort_by(|a, b| b.cmp(a)); biased_points .iter() .take(x[1]) .fold(0, |sum, item| sum + item) .abs() }) .fold(0, |sum, item| max(sum, item)) ) }
絶対値が最大となる場合であるのでアルゴリズム的には各々の評価指標が負に大きいか正に大きいかを全通り探索($2^{3}=8$通り)すればよい.
しかしまあ,Rustの使い方が全く分からずかなり*1苦戦した.
*1:4時間くらい