Quiz
https://codeforces.com/contest/1165/problem/F2
Submission
https://codeforces.com/contest/1165/submission/54169433
解法（引用）
F:答え決め打ってにぶたん 「x日までに買えるか」の判定問題にした場合、最適な買い方は、「x日までにセールが無いならx日目に買う セールがあるなら、x日までのうち最後のセール日に買えるだけ買い、残りはx日目に買う」
— こるとん (@kyort0n) 2019年5月14日
その他
- 補助用の配列をいくつか作って、実装が重め
- これを時間内に書けている人たち、すごい
二分探索
- 普段、私は二分探索をleft = 0, right = inf などでやっている
- しかし今回の解法を見ると分かるように、日にちを決め打った時にシミュレーションして判定している
- なのでinfではだめで、制約に「kの和は200000以下」と書かれているので、right = infではなく、その値を入れることでシミュレート可能になる
学び
- 二分探索の上限を適切に決めると、判定にシミュレーションが使える
