ABC116-Cで素晴らしい回答をしている方を発見した
自分で書いたときは、与えられたhをリストに格納し、左から０でない部分を探し設問のlに、次いでlから右に向かって一番初めに見つかった0の手前を設問のrとして、[l:r+1]の範囲で最小の値を見つけ、h[l:r+1]からその値を減算すると同時にansに最小値を加算する、というのを、lがリスト終端になるまで繰り返した。設問の制約上、花の数Nが100本までなので、上記方法でもO(N^2))ぐらい？で十分間に合うのだが、Nの範囲が増えると処理が間に合わなくなることが予想されて、なんかあんまりしっくりこなかった。
調べてみるとすごい回答をしている方を発見した。
ある花について目標高さまで水を与えたときに、その右隣も同じ高さまでなら同時に成長させられることを利用することで、複雑なループや分岐なしに目標を達成している。これだとO(N)で終わるので、花が10^5までは十分に間に合う。この解法は思いつかなかったので感動した。短い時間でこういうスマートな回答を思いつけるようになりたい。
