問題の概要

　 $N \ (1 \leq H \leq 5 \times 10^{5})$ 日の間、初期値 $H \ (1 \leq H \leq 10^{9})$ の満腹度を $0$ 以下にさせないために、以下のような食事のいずれかを選ぶ。

　以上の条件を満たす必要最低限の食費はいくらかを求める。また、満腹度には上限がない上、 $N$ の値の範囲で以下のように部分点が設定されている。

範囲	$N \leq 10$	$N, H, B, D \leq 50$	$N \leq 1000$	$N \leq 5 \times 10^{6}$
点数	10	40	100	101

問題の考察

　普通の食事の日数を $X$ 日、質素な食事の日数を $Y$ 日とする。

　この時、満腹度には上限がないため、最初の $X + Y$ 日に全ての食事を済ますと考える。この方法では、満腹度が途中で $0$ になる状態を考えずに、食費の最小値を求めることができる。

　各 $(X, Y)$ に対して、以下の不等式が成り立つかどうかを確認する。

$H + BX + DY - (N - X - Y)E > 0 \ \cdots \ (1)$

　しかし、この解放では $O(n^{2})$ であるため、 $N \leq 5 \times 10^{6}$ のテストケースでは時間が足りない。

　式 (1) を以下のように式変形すると $X$ のみの探索で済むため、 $O(n)$ で求めれる。

$Y > \frac{(N - X)E - H - BX}{D + E} \ \cdots \ (2)$

　また、 $X$ の値が大きいとき、 $Y$ の値が負の値をとることがあるため、注意が必要となる。

　この解法では、式 (1) をそのまま用いる。 $(X, Y)$ の探索を、以下のように尺取り法を用いることで、 $O(n)$ で探索することを可能とした。

　以上のソースコードは以下のGithub上にて参照可能です。 github.com