ABC 013 C - 節制

• 問題
• AC

実数$x$より大きい最小の整数は$\lfloor x \rfloor +1$（あるいは$\lfloor x + 1 \rfloor$）である。間違えて$\lceil x \rceil$としてしまったのが２回目なのでメモ。

普通の食事を$i$日、質素な食事を$j$日取るとすると、最終日の満腹度は$H + Bi + Dj - E(N-i-j)$であり、これが正でなければならない。逆に、前半に食事をし続けて後半に食事を抜けば初日か最終日に満腹度が最小になるので、最終日の満腹度が正になるような$(i, j)$については、常に満腹度が正になるような食べ方が存在することになる。したがって次の問題に帰着する。

$\begin{gathered} \text{Minimize} \ Ai + Cj \\ \text{subject to} \qquad H + Bi + Dj - E(N-i-j) > 0 \\ i \ge 0, j \ge 0, i+j \le N \end{gathered}$

$i$も$j$も小さければ小さいほどよいので、各$i \in \{0, ..., N\}$について条件を満たすような最小の$j$だけ調べればよい。具体的には$j = \max (0, \lfloor (EN-H-(B+E)i)/(D+E) \rfloor + 1)$として$Ai+Cj$の最小値を全探索する。（ただし$i+j \le N$を満たしていないものは除く。）${\mathcal O}(N)$。