https://atcoder.jp/contests/abc336/tasks/abc336_d
左から見て、その位置からどこまでがピークになり得るかを調べます。右からも同様です。
入力例1だとそれぞれ0-basedで、
2 2 2 3 4 0 0 1 2 4
そして、上の左から見ていって、2以下で一番右の場所を探します。そうすると、index: 3が2になります。長さは4ですが、ピラミッドは奇数なので長さ3で、サイズは2です。つまり、ある数以下で最も右の位置を探せばよいです。
// Pyramid #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } //////////////////// Segment Tree //////////////////// struct SegmentTree { n: usize, v: Vec<usize>, } impl SegmentTree { fn ceil_two_pow(n: usize) -> usize { if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 } } fn create(B: Vec<usize>) -> SegmentTree { let m = B.len(); let n = SegmentTree::ceil_two_pow(m); let mut v: Vec<usize> = vec![B.len(); n*2-1]; for i in n-1..n-1+m { v[i] = B[i+1-n] } for i in (0..n-1).rev() { v[i] = min(v[i*2+1], v[i*2+2]) } SegmentTree { n, v } } fn rightmost_le_pos(&self, m: usize) -> usize { self.rightmost_le_pos_core(m, 0) } fn rightmost_le_pos_core(&self, m: usize, i: usize) -> usize { if i >= self.n - 1 { i + 1 - self.n } else { if self.v[i*2+2] <= m { self.rightmost_le_pos_core(m, i*2+2) } else { self.rightmost_le_pos_core(m, i*2+1) } } } } //////////////////// process //////////////////// fn read_input() -> Vec<usize> { let _N: usize = read(); let A = read_vec(); A } fn find_right_limit(A: &Vec<usize>) -> Vec<usize> { let N = A.len(); let mut L: Vec<usize> = vec![N-1; N]; let mut j: usize = 0; for i in 0..N-1 { while j < N && 1 + j <= A[j] + i { j += 1 } L[i] = j - 1 } L } fn find_left_limit(A: &Vec<usize>) -> Vec<usize> { let N = A.len(); let mut L: Vec<usize> = vec![0; N]; let mut j: usize = N - 1; for i in (1..N).rev() { while 1 + i <= A[j] + j { if j == 0 { break } j -= 1 } L[i] = j + 1 } L } fn F(A: Vec<usize>) -> usize { let N = A.len(); let L = find_right_limit(&A); let R = find_left_limit(&A); let tree = SegmentTree::create(R); let mut max_size = 0; for i in 0..N { let j = tree.rightmost_le_pos(L[i]); max_size = max(max_size, (j - i + 2) / 2) } max_size } fn main() { let A = read_input(); println!("{}", F(A)) }