[AtCoder] ABC116 C – Grand Garden

Grand Garden

https://atcoder.jp/contests/abc116/tasks/abc116_c

考え方

題意

連続した区間に水をやる操作を \( 1 \) 回と数えたとき、条件を満たす操作回数の最小値を答えます。

方針

隣り合う花の高さを比べたとき、\( \max(h_i, h_{i + 1})\) 回水やりを行う必要があることに気が付きます。

まず初めに、番号 \( 1 \) に対して水をやる事を考えると、\( h_1 \) 回水をやる必要があります。このとき、番号\( 2 \) の花の高さが \( h_1 \) 以下であれば、\( 2 \) の花には水をやる必要がありません。逆に大きければ、\( h_2 – h_1\) 回水を追加であげる必要があります。次に、\( 3\) の花に影響するのは、\( h_2 \) の高さであることが分かります。

したがって、

\[ \displaystyle h_1 + \sum_{ i = 1 }^{ n – 1 } \max(0, h_{i + 1} – h_i) \]

が答えになります。

コード

上記の方針のコード

コンテスト中に考えたコード

実際にシミュレーションを行ったコードです。

水を上げていく中で \( 0 \) でない連続する区間の最小値を足していく方法です。

感想

シミュレーションの方は \( N \) が大きくなると厳しいので、上記の方針のような考え方を身につけたいですね。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする