BAPC2018 F - Financial Planning - ツバサの備忘録

問題

$N$ 個の投資先があり、 $i$ 番目の投資先は、費用が $c_{i}$ (初日のみ)で、1日に $p_{i}$ ユーロの利益が出ます。
投資費用を返済した上で $M$ 円の利益を得るために必要な最小日数を答えてください。
というものになります。
$1 \leqq N \leqq 10^{5}$
$1 \leqq M \leqq 10^{9}$
$1 \leqq c_{i} \leqq 10^{9}$
$1 \leqq p_{i} \leqq 10^{9}$
です。

解法

二分探索をして答えを出します。
すると、結局調べたいものは $X$ 日で利益 $M$ 円を出すことができるかどうか、になります。
これを $O(N)$ で求めることができればよいです。
さて、 $i$ 番目の投資先に投資して $X$ 日経つと、利益は $p_{i} \times X$ ユーロになります。
すると、 $c_{i}$ ユーロの費用が必要だったので、 $p_{i} \times X - c_{i}$ が最終的な利益になります。
この値が正であれば投資をし、0以下であれば投資をしない、とすれば、 $X$ 日かける場合の最大利益を出すことができます。
よって、 $p_{i} \times X - c_{i}$ が正となるような投資先の合計値が $M$ を超えていれば、 $X$ 日で利益 $M$ 円を出すことができ、そうでなければできないことになります。
また、 $X$ 日で利益 $M$ 円を出すことができる場合、同じ投資先だけを選べば、 $X+1$ 日で少なくとも利益 $M$ 円を出すことができます( $p_{i}$ は正の値だからです)。よって、 $X$ 日を二分探索で求めることができます。

感想

考察自体はぱっとできました。が、利益の合計を求める際に、long long型ですらオーバーフローする可能性があったことを考慮しきれておらず、WAを2,3回だしました。おそらく英語を解読する方が考察より長かったと思います…
思考の流れとしては、投資先の選び方が無数にあり、そっちから攻めるのが難しそう→日にちを固定してみればどうだろうか、となったところで、まず $X$ 日と固定して二分探索をする方法が思い浮かびます。
そして、 $X$ 日目に利益が出ているものだけを選べばよいので、 $O(N)$ で計算できそう、ということで全体としても時間内に計算ができそう！という感じでした。
最後に、最悪ケース(二分探索の端)の計算と、単調性の簡単な裏付けをとって実装、という形です。