つらら(10本選3) - olpheの競プロ帖

N本のつららがあり、左右に自分より長いつららがなければ伸びていく。

長さがLを越えると折れてしまうので、全部折れるまでにどれだけかかるかな？という問題。

毎秒シミュレートしては間に合わないので他の方法を取る必要がある。

まず、最初の段階で伸びるつららに関しては何秒で折れるかはすぐにわかる。

最初に自分より長いつららが隣にあるつららは、隣にある自分より長いつららが全て折れてから伸び始めることもわかるので、隣にある自分より長いのつららが折れるまでの時間の最大値に自分が伸び始めてから折れるまでの時間を足せばよいことが分かる。

再起関数で解いた。計算量は多分O(N)

難易度は7程度に感じられた。