E - Espresso

2 secs 1024 MB

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

問題原案：@uni_kakurenbo

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

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

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

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

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

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

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

問題の内容を数式を用いて整理してみましょう．を「のなかで番目に小さい値」とすると，

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

の条件式を変形すると，

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

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

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

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

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

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

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