ABC116 C - Grand Garden - ツバサの備忘録

問題
提出コード

解法

こちらの問題とほぼ同じ考え方をすることができます。
スタックを利用します。
現在のスタックの一番上の数字を $s$ とします。最初は $0$ を格納しておきます。
そして以下のような操作を繰り返せば、答えが求まります(初期値は0としておきます)。

$s \lt h_{i}$ のとき
スタックに $h_{i}$ をそのままプッシュします。新しい $s$ は $h_{i}$ となります。
$s = h_{i}$ のとき
なにもせず進みます。
$s \gt h_{i}$ のとき
$s \leqq h_{i}$ となるまで、以下の操作を繰り返せばよいです。
$s$ の次のスタックの数字を $t$ とします。
答えに、 $s - max(t,h_{i})$ を追加します。
繰り返したのち、 $s \leqq h_{i}$ になったら上の操作を行います。

これを繰り返すと、最終的な答えが求まります。また、最後に $h_{N+1} = 0$ を行うことにも注意してください。

感想

こちらの問題を解いていたため、ほぼ同じ解法に帰着させることができました。
京都大学プログラミングコンテスト(KUPC)2013 - ツバサの備忘録
今回は、前回と違い、答えの計算をスタックのトップより今見ている値が小さくなったら、にしたのですが、明らかに前の方が実装が軽いですね。
思考の流れとしては、「あ、この問題前見たことある、スタック使えばいいやつ！」
から、スタックの先頭と比べた時にどの条件だったらどうすればいいか、を丁寧に考えていく感じです。
想定解を見たら、全然違う解法でびっくりしたのですが、よくよくみたら制約がKUPCの問題に比べてとても少なかったです…(おそらく、解法を両方思いついていても、実装は今回の方が軽いのでこちらを選択すると思います)