Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 246 C問題 Coupon

AtCoder ABC ABC246 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個の商品があり, $i$ 番目の商品は $A_i$ 円である.

クーポンを $K$ 枚持っており, $a$ 円の商品に対して $k$ 枚のクーポンを消費すると, その商品を $\max(a-kX, 0)$ 円で買うことができる.

全ての商品を買うためには最低でも何円必要か.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq K,X \leq 10^9$
$1 \leq A_i \leq 10^9$

解法

(割引後の総和)=(元々の総和) $-$ (割引額) なので, 割引額の最大化を目指す.

$X$ 円以上の商品があるのに, $X$ 円未満の商品に対してクーポンを使用することは割引額の最大化に反してしまう.

よって, 方針としては, まず, 全ての商品を $X$ 円未満にすることである. 元々 $a$ 円の商品を $X$ 円未満にするためには, $\left \lfloor \frac{a}{X} \right \rfloor$ 枚のクーポンが必要である.

$\displaystyle M:=\sum_{i=1}^N \left \lfloor \frac{A_i}{X} \right \rfloor$

とする. このとき, $K \leq M$ であるとき, 割引額は明らかに $KX$ 円以下であり, $KX$ 円の割引を達成する事が可能である.

以降では $K \gt M$ とする. このとき, $B_i$ を $A_i$ を $X$ で割った余りとする. 残り $K':=K-M$ 枚のクーポンを用いて, 割引額の最大化を達成するためには, $B_i$ の大きい順にクーポンを使用すれば良い ( $K' \leq N$ の場合は $N$ 枚だけ使えば十分).

以上から, $B_1, \dots, B_N$ を降順に並び替えた列を $C_1, \dots, C_N$ とし, $M':=\min(K', N)$ とする. $Y$ を

$\displaystyle Y:=\begin{cases} KX & (K \leq M) \\ \displaystyle MX+\sum_{i=1}^{M'} C_i & (K \gt M) \end{cases}$

とすると, 答えは $\displaystyle \sum_{i=1}^N A_i-Y$ である.

時間計算量は $C_1, \dots, C_N$ を求めるためのソートがボトルネックになり, $O(N \log N)$ である.