2023-05-31 iPad 思ったより重かった / ABC236 E を解いた

iPad (10th generation) に Expo Go などをインストールして動作確認。大きいし重い……。

USB Type-C が使えるもので安価なものを選んだのだけど、大きさももうすこし考えれば良かったかも……。

ABC236 E - Average and Median (AtCoder Beginner Contest 236:E問題) https://atcoder.jp/contests/abc236/tasks/abc236_e
- https://atcoder.jp/contests/abc236/submissions/41874247
- 解説 AC
- 平均を a_1 + a_2 + ... + a_k >= k * mid を (a_1 - mid) + (a_2 - mid) + ... + (a_k - mid) >= 0 のようにして全体から mid を引いた形にする点が面白い
- 中央値を mid 以上の個数のほうが多い、だけでなく 1 or -1 にしてこちらもの sum > 0 の問題にしてしまう点も面白い

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }

    let mut ok = 0_f64;
    let mut ng = 1_000_000_001_f64;
    for _ in 0..100 {
        let mid = ok + (ng - ok) / 2_f64;
        let b = a
            .iter()
            .copied()
            .map(|a_i| a_i as f64 - mid)
            .collect::<Vec<f64>>();
        let mut dp = (0_f64, 0_f64);
        for b_i in b.iter().copied() {
            dp = (dp.1, dp.0.max(dp.1) + b_i);
        }
        if dp.0.max(dp.1) >= 0_f64 {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    println!("{}", ok);

    let mut ok = 0_i64;
    let mut ng = 1_000_000_001_i64;
    while ng - ok > 1 {
        let mid = ok + (ng - ok) / 2_i64;
        let b = a
            .iter()
            .copied()
            .map(|a_i| if a_i >= mid { 1 } else { -1 })
            .collect::<Vec<i64>>();
        let mut dp = (0_i64, 0_i64);
        for b_i in b.iter().copied() {
            dp = (dp.1, dp.0.max(dp.1) + b_i);
        }
        if dp.0.max(dp.1) > 0_i64 {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    println!("{}", ok);
}

今日のコミット。