ABC189 C を解いた

• Mandarin Orange (AtCoder Beginner Contest 189:C問題) https://atcoder.jp/contests/abc189/tasks/abc189_c
  • https://atcoder.jp/contests/abc189/submissions/43915362
  • 以前は O(N²) 解法で解いていた
  • 嘘解法かと思ったけど公式の解説でもそうなっているのでたぶんそれで良さそう
  • 書籍に記載の O(N) 解法は left の位置を設定できなかったりして 7WA
  • 書籍の大小判定も間違っている気がする > ではなく >= のような気がする

// O(N)
use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n],
    };
    a.push(0);
    let mut max = 0_usize;
    let mut stack: Vec<(usize, usize)> = vec![];
    for (i, a_i) in a.iter().copied().enumerate() {
        let mut left_index = i;
        while let Some((l, a_l)) = stack.pop() {
            match a_l.cmp(&a_i) {
                std::cmp::Ordering::Less => {
                    stack.push((l, a_l));
                    break;
                }
                std::cmp::Ordering::Equal => {
                    left_index = l;
                    max = max.max(a_l * (i - left_index));
                }
                std::cmp::Ordering::Greater => {
                    left_index = l;
                    max = max.max(a_l * (i - left_index));
                }
            }
        }
        stack.push((left_index, a_i));
    }
    let ans = max;
    println!("{}", ans);
}

// O(N^2)
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    };
    let mut ans = 0_usize;
    for l in 0..n {
        let mut max = a[l];
        for r in l..n {
            max = max.min(a[r]);
            ans = ans.max(max * (r - l + 1));
        }
    }
    println!("{}", ans);
}

---

今日のコミット。

• genpi 1 commit
  • Add names cache
• rust-atcoder 1 commit
  • pastbook2 abc189_c