ABC013-C 節制

 概要

https://atcoder.jp/contests/abc013/tasks/abc013_3

N回次の3つの操作を選択する。初期値をHとする値hが一度も0にならないようにするとき、コストの最小値を求めよ。

・コストA払い、hにBを加算する

・コストC払い、hにDを加算する(C<A かつ D<B)

・コストは変化せず、hにEを減算する

解法

すべての日について3つ目の選択肢を選んだ場合、hはNEだけ減少する。

このとき、コストを払う選択肢を選ぶよう変更すると、最終的なhは(例えば)B+E増加する。

hが0以下になることが許されないので、求める答えはコストを払う選択肢をN回以下選択することで、H-NEを正の値にできる最小のコスト ということになる。

これは、以下の2つのパターンで

・k日間、1つ目の選択肢を取り続けたとして、H-NEに満たない場合については2つ目の選択肢を足りない分だけ加える

とすると、各日についてO(1)で払うコストを求めることができるので、全体としてO(N)で解を求められる。

https://atcoder.jp/contests/abc013/submissions/20193158