昨日で中級編の問題をすべて解き終えたので『アルゴリズム実技検定 公式テキスト[上級]~[エキスパート]編』を読みはじめた。 https://book.mynavi.jp/ec/products/detail/id=135840
あとは iPad を買った。気は進まないけど必要なので仕方ない。
ShiftIt の代わりに Hammerspoon を導入した。ひさしく諦めていたのだけど「ウィンドウを操作するショートカットキーは必要だ」と思い直した次第。
- PAST #1 M - おまかせ (第一回 アルゴリズム実技検定:M問題)
https://atcoder.jp/contests/past201912-open/tasks/past201912_m
- 解説 AC
- 解説を読んだあとは「知識的には解けたはずなのに」と思った
- 書籍の流れ的に二分探索なのは明らかだ
- 式を整理して
(B_i - X * A_i) + ... >= 0
に整理できれば解けたはず……
use proconio::input; fn is_ok(ab: &mut [(i64, i64)], cd: &mut [(i64, i64)], x: f64) -> bool { ab.sort_by(|&(a1, b1), &(a2, b2)| { (b1 as f64 - x * a1 as f64) .partial_cmp(&(b2 as f64 - x * a2 as f64)) .unwrap() }); cd.sort_by(|&(c1, d1), &(c2, d2)| { (d1 as f64 - x * c1 as f64) .partial_cmp(&(d2 as f64 - x * c2 as f64)) .unwrap() }); ab.iter() .copied() .rev() .take(5) .map(|(a, b)| (b as f64 - x * a as f64)) .sum::<f64>() >= 0_f64 || ab .iter() .copied() .rev() .take(4) .map(|(a, b)| (b as f64 - x * a as f64)) .sum::<f64>() + cd.iter() .copied() .rev() .take(1) .map(|(c, d)| (d as f64 - x * c as f64)) .sum::<f64>() >= 0_f64 } fn main() { input! { n: usize, m: usize, mut ab: [(i64, i64); n], mut cd: [(i64, i64); m], } let mut ok = 0_f64; let mut ng = 1_000_000_000_f64; for _ in 0..100 { let x = ok + (ng - ok) / 2_f64; if is_ok(&mut ab, &mut cd, x) { ok = x; } else { ng = x; } } let ans = ok; println!("{}", ans); }
今日のコミット。
- tsukota 8 commits
- rust-atcoder 1 commit