AtCoder ABC #133 D - Rain Flows into Dams

D - Rain Flows into Dams

反省

二分探索で解けると思ったが、上限下限が決定できるような問題じゃなかった。

解説

に気づけたら実装は簡単。

fn solve(aa: &[i64]) -> Vec<i64> {
    let s = aa.iter().fold(0, |sum, i| sum + i);

    let x1 = s - 2 * aa.iter().skip(1).step_by(2).fold(0, |sum, i| sum + i);

    let mut ans = Vec::new();

    aa.iter().fold(x1, |x, a| {
        ans.push(x);
        (a - x / 2) * 2
    });

    ans
}

しまった、step_by()はRust 1.28からだった。。。

fn solve(aa: &[i64]) -> Vec<i64> {
    let s = aa.iter().fold(0, |sum, i| sum + i);

    let x1 = s - 2 * {
        let mut acc = 0;
        for (i, &a) in aa.iter().enumerate() {
            if i % 2 == 0 {
                continue;
            }
            acc += a;
        }
        acc
    };

    let mut ans = Vec::new();

    aa.iter().fold(x1, |x, a| {
        ans.push(x);
        (a - x / 2) * 2
    });

    ans
}