AtCoder Beginner Contest 047-D - プログラムのお勉強メモ

概要

くじかつで AtCoder Beginner Contest 047 D を解いたのでメモ
実験的にわざと rust でNlog(N) のループを書いたけど TLE でした
- プログラミング言語が速いからといって計算量は甘えさせてくれないという良い教訓になりました

問題概要

初期の街から n 個目の街まで順番にまわって商品を売ったり買ったりできる(前の街には戻れない)
各町では商品の価格が異なる
一番利益が出る箇所を妨害したい
どこかの街の商品価格を1円上下させると1コストかかるが, 最低で何コストかければ最大売上金額に1円でも打撃を与えられるか答えろ

方針

一番売り買いして得する箇所が何個あるか数え上げる
その場所を1円上げてやれば一番高く売れる箇所に打撃を与えられる

実装(rust)

fn main() {
    let (n, t) = input!(usize, usize);
    let a = input!(usize; "vec");

    let mut result_map: HashMap<usize, usize> = HashMap::new();
    let mut min_val = a[0];

    for i in 1..n {
        let val = a[i].checked_sub(min_val).unwrap_or(0);
        if val > 0 {
            let v: usize = match result_map.get(&val) {
                Some(x) => x + 1,
                None => 1,
            };
            result_map.insert(val, v);
        }
        match min_val.cmp(&a[i]) {
            std::cmp::Ordering::Greater => min_val = a[i],
            _ => {}
        }
    }

    let (k, v) = result_map.iter().max_by(|x, y| x.0.cmp(y.0)).unwrap();
    println!("{}", v);
}

例によって入力は省略

所感

最初は2重ループ (n * logN) で実施したが見事に TLE が出たため方針変更
片方向にしかいかないのでそれまでの最低金額をメモすれば最大利益を計算し続けられることに気づいた