JOI難易度６ つらら

問題原文

https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf#page=7

問題要旨

本のつららが横一列に並んでいる。 番目のつららの長さは である。
つららは、両隣のつららよりも自身が長い時 に、毎秒１cmずつ伸び、 cmになると折れる。（折れたつららは以後 0cmとして扱う）
全てのつららが折れるまでにかかる時間は何秒か？なお、最初隣り合うつららの長さは相異なる。

• 
• 

解法

いろんな方法があると思うけど、メモ化再帰が直感的だと感じる。
例えば、あるつらら に着目した時、そのつららが両隣のどちらよりも小さい時、そのつららが折れるまでの秒数は、
max( 番目のつららが折れるまでの秒数, 番目のつららが折れるまでの秒数) + - になる。

実装

番兵を置いとくと少し楽。

import sys
sys.setrecursionlimit(10 ** 9)

N, L = map(int, input().split())
A = [int(input()) for _ in range(N)]
MIN = min(A)
A = [-1] + A + [-1]  # 番兵追加

memo = [-1] * len(A)

# 左からi番目のつららが折れるまで何秒かかるか
def calc(i):
    if memo[i] > 0:
        return memo[i]

    if (A[i] > A[i - 1]) and (A[i] > A[i + 1]):
        ret = max(0, L - A[i])

    elif A[i - 1] < A[i] < A[i + 1]:
        ret = max(0, L - A[i] + calc(i + 1))

    elif A[i + 1] < A[i] < A[i - 1]:
        ret = max(0, L - A[i] + calc(i - 1))

    else:
        ret = max(0, L - A[i] + max(calc(i - 1), calc(i + 1)))

    memo[i] = ret
    return ret

for i in range(1, N + 1):
    memo[i] = calc(i)

print(max(memo))

感想

かなり好きな問題。
他の方法でも今度解いてみよう。。。