2023-05-29 アルゴリズム実技検定公式テキスト上級編を読みはじめた / PAST #1 M を解いた

昨日で中級編の問題をすべて解き終えたので『アルゴリズム実技検定　公式テキスト［上級］～［エキスパート］編』を読みはじめた。 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);
}

今日のコミット。