AtCoder Beginner Contest 013 C - 節制
C - 節制
時間制限 : 2sec / メモリ制限 : 256MB
問題文
セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。
高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間、できるだけ食費を抑えて節約生活を送ることにしました。
はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。
普通の食事: A 円の出費をして、満腹度が B 増える。 質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C<A かつ D<B） 食事抜き: 出費なしで、満腹度が E 減る。 厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。
高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？
ただし、高橋君は超人級の胃袋を持っており、その満腹度には上限がないとする。すなわち、いくら食事をしても高橋君の満腹度が頭打ちになることはない。
note
変数が2つ（普通の食事をとる数a, 質素な食事をとる数b, 食事抜きの日数n- a-b)あり、aの値を固定してあげると、Ba + D b + H - E *(N - a - b) > 0の関係より、bの範囲が決まる bはこの範囲を満たす最小の値を使えば良いので、aの値を全列挙すれば、答えが求まり計算量はO(N)。 最近この手の方程式を値固定して解くやつに多く当たる気がする。
