ABC336 D - Pyramid

atcoder.jp

問題

• 数列Aが与えられるので、Aの中に入り込むピラミッド数列の最大の大きさは？
• ピラミッド数列とは？
  • 1,2,...k-1,k,k-1,...,2,1みたいなやつ（長さ2k-1)

成約

• $ 1 \leq N \leq 2 \times 10^{5}$
• $ 1 \leq A_i \leq 10^{9}$

思考

• 成約から、長さ1のピラミッド数列は絶対作れるねぇ
• じゃあ、2は…？3は…？
  • これを最大まで見ていくと、にぶたんでも判定に$O(N²)$で禿げますね
• ピラミッド数列は左右対称なので、左半分と右半分でそれぞれ判定していきたい
  • iを頂点とするピラミッド数列を作りたいです
    • iを頂点にした時に作れる、一番大きいピラミッド左半分は？
      • 累積minで作れるね
      • 右半分も同じように作れるね
  • iを頂点にして作れる右半分ピラミッドと左半分ピラミッドのうち、小さい方は？
    • O(N)で前準備できるし、O(N)で確認できるね
• 分かれば楽なんだけど、正直実装で添字ガチャしがち…

コード

N = int(input())
A_L = list(map(int, input().split()))

L = [0]*(N+2)
R = [0]*(N+2)

# L[i]: iを頂点とした時に作れる最大の左半分ピラミッド数
# R[i]: iを頂点とした時に作れる最大の右半分ピラミッド数
for i in range(N):
    L[i+1] = min(L[i]+1,A_L[i])
for i in range(N-1,-1,-1):
    R[i+1] = min(R[i+2]+1,A_L[i])

ans = 1
for i in range(N):
    ans = max(ans, min(L[i],R[i]))

print(ans)