これのバチャをしました。
ボス問を解説するつもりでやっていますが、ボス前のほうが難しかったので、そっちをやります。
問題概要
Polycarp 君は 円稼ぎたいです。彼が1日のうちに取れるアクションは、現在の彼のレベルを
として、
- a[x] 円稼ぐ
- b[x] 円払い、レベルを一つ上げる
のいずれかです。ここで、a は単調増加数列です。Polycarp 君は最短何日で 円以上稼げるでしょうか？
解法
僕が所属していたサイクリング部に伝わることわざとして、『どうせ買うなら早いほうが良い。』があります。これは、『後々買うものであるなら、先に買ったほうがその恩恵を早く受けられて得である。』という意味です。
今回の問題も同様に、どうせ出世するなら必要なコストは同じであるので、早いほうが良いです。したがって、最後のレベルを固定して最速でそのレベルまで駆け上がり、 円貯めるために必要な日数の最小値を求めれば良いです。
僕は最小値を求めれば良いことに気づかず、二分探索をしました。
