Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

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)。 最近この手の方程式を値固定して解くやつに多く当たる気がする。