E - Espresso

概要

浮動小数点数の誤差に注意しましょう．

問題原案：@uni_kakurenbo

解説

$Ⅰ.$ 貪欲法

この問題は「貪欲法」という手法を用いて解くことができます．

まず，前提として必要な砂糖の質量は飲むコーヒーの量に比例します．(比例定数は $\frac{X}{Y}$ です．)
つまり「飲めるコーヒーの杯数をできるだけ多くしたい」という状況のもとでは，一杯当たりのコーヒーの量ができるだけ少なくなるようにカップを選んだほうがよいということになります．

したがって，「必要な砂糖の質量の総和が $K$ を超えない間，まだ選んでいないカップのうちで入っているコーヒーの量が最も少ないものを選び続ける」ことで答えを求めることができます．

あらかじめ入っているコーヒーの量が少ない順になるようにカップをソートしておくとよいでしょう．

$Ⅱ.$ 浮動小数点数の誤差

とはいっても，先述の内容をそのまま実装しても AC を得ることはできません．

多くの言語で小数の表現には「浮動小数点数」というものが用いられていますが，この浮動小数点数には通常誤差が生じます．
この問題においてもこの誤差の影響によって正しい答えが求められなくなる場合があるので注意が必要です．

$Ⅲ.$ 数式の導入

実は，この問題は整数のみの演算によって解くことができます．

問題の内容を数式を用いて整理してみましょう． $B_i$ を「 $(A_1, A_2, \ldots, A_N)$ のなかで $i$ 番目に小さい値」とすると，

$$\sum^L_{i=1} \frac{X}{Y} B_i \leq K$$

を満たす $L$ の最大値を求めればよいことになります．

$L$ の条件式を変形すると，

$$X \sum^L_{i=1} B_i \leq KY$$

が得られ，これは整数の演算のみによって判定することができます．

実際の解答ではこれを用いるとよいでしょう．

$Ⅳ.$ 計算量

時間計算量はソートがボトルネックとなり，たいていの言語と処理系で $O(N \log N)$ です．

$Ⅴ.$ 発展

$1)$ ボーナス問題

解説はこのページの下部にあります

• $K$ について $T \scriptsize \hspace{0.2em} (1 \leq T \leq 10^4)$ 個のテストケース $K_1, K_2, \ldots, K_T$ があたえられます．
  $\, t \scriptsize \hspace{0.2em} (1 \leq t \leq T)$ 個目のテストケースでは $K=K_t$ として答えを求めてください．
  $K$ 以外の入力についてはすべてのケースで同一とします．

$2)$ 類題

(難易度順)
解法自体は同類ではないものも含まれます．

• ABC 189 $\hspace{0.15em}$ B - Alcoholic
• ABC 246 $\hspace{0.15em}$ C - Coupon
• ABC 223 $\hspace{0.15em}$ C - Doukasen

実装例

$\\$

ボーナス問題(解答)

あらかじめ $B_i$ について累積和を取っておけば，条件を満たす $L$ の最大値を二分探索によって各テストケースあたり時間計算量 $O(\log N)$ で求めることができます．
全体で $O((N+T) \log N)$ です．

余談

テストケースを用意するのがくっそ大変でした。
long double をちゃんと落すの難しすぎ。