bouzuya.hatenablog.com

ぼうずやのにっき

朝から仕事 / ABC336 D

朝から仕事。個人プロジェクトの焼き直しみたいなコードを書いている。

ABC336 : AtCoder Beginner Contest 336

  • D - Pyramid https://atcoder.jp/contests/abc336/tasks/abc336_d
    • 提出: https://atcoder.jp/contests/abc336/submissions/49413827
    • 多い分は減らせるし、不要な要素は削れる
    • 最終的な形は 1 つずつ増えてどこかから 1 つずつ減る「山」をつくればよい
    • 1 つ前の要素 + 1 といまの要素の小さい側がその位置でつくれる最大になる
    • この数列を左からと右からの両方でつくって各位置の最小値がその位置でつくれる最大の山になる
    • 山のうち最大値が答えになる
use proconio::input;

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

    let mut b = vec![1; n];
    let mut p = 0_usize;
    for (i, a_i) in a.iter().copied().enumerate() {
        p = (p + 1).min(a_i);
        b[i] = p;
    }

    let mut c = vec![1; n];
    let mut p = 0_usize;
    for (i, a_i) in a.iter().copied().enumerate().rev() {
        p = (p + 1).min(a_i);
        c[i] = p;
    }

    let ans = b
        .into_iter()
        .zip(c.into_iter())
        .map(|(b_i, c_i)| b_i.min(c_i))
        .max()
        .unwrap();
    println!("{}", ans);
}

今日のコミット。