No.31

すべてのジュースは最低1リットル買わなければいけないので, 最初に買っておいて $V = V - N$ としておく. $V \leq 0$ となった場合はすべてのジュースを等分にすればいい.

あるジュースを小数点以下のリットル使った場合, その他のジュースを小数点以下のリットル補わなければいけないので無駄となるので, すべて整数リットルで考えていい.

問題は,

$$p_1 + p_2 + \cdots + p_N \geq V \\ p_1 \geq p_2 \geq \cdots \geq p_N \geq 0$$

の条件下で

$$S = p_1C_1 + p_2C_2 + \cdots p_NC_N$$

として $S$ の最小値を求める問題となる.

ここで, 割合の小さいジュースから順に買うとすると, $i$ 番目のジュースを買うためには $1 \dots i - 1$ 番目のジュースも買わなければいけない. この考え方を使うと問題は

$$q_1 + 2q_2 + \cdots Nq_N \geq V \\ q_i \geq 0$$

の条件下で

$$S = q_1D_1 + q_2D_2 + \cdots q_ND_N$$

s.t.

$$D_i = \sum_{j = 1}^i C_i$$

として $S$ の最小値を求める問題に変形できる.

これはナップザック問題と似たような問題であるが DP で解くとなると $O(NV)$ の計算量となり間に合わない.

そこで単位単価 $D_i/i$ が最も安いジュースをなるべく多く買うようにする. このジュースを $k$ として, $k$ 以外のジュース $m$ を $mk$ リットル買うとすると, それよりは $k$ を $mk$ リットル買う方が総コストが安くなるので, $m$ は $mk$ リットル未満しか買わないことになる. すなわち, $q_m \lt k$ である.

また, $k$ 以外のジュースをあわせて $k$ 個買ったとし, それらを $r_1, r_2, \dots, r_k$ として,

$$r1 + r2 + \dots + r_t \equiv s_t \pmod k \qquad (t = 0, 1, \dots, m)$$

と置くと, 鳩の巣原理より $s_i = s_j$ となる $i, j$ が存在し, このとき

$$r_{i + 1} + r_{i + 2} + \dots + r_j \equiv 0 \pmod k$$

となる. よって $r_{i + 1} + r_{i + 2} + \dots + r_j$ は $k$ の倍数であるから, $k$ のジュースに置き換えられるので, $k$ 以外のジュースをあわせて $k$ 個以上買うことはない. したがって, $k$ 以外のジュースの総量は $kN$ に抑えられ, 先の $q_m \lt k$ と合わせると DP の時間計算量は $O(N^4)$ となる.