F2. Microtransactions (hard version)

Quiz

https://codeforces.com/contest/1165/problem/F2

Submission

https://codeforces.com/contest/1165/submission/54169433

解法(引用)

その他

  • 補助用の配列をいくつか作って、実装が重め
  • これを時間内に書けている人たち、すごい

二分探索

  • 普段、私は二分探索をleft = 0, right = inf などでやっている
  • しかし今回の解法を見ると分かるように、日にちを決め打った時にシミュレーションして判定している
  • なのでinfではだめで、制約に「kの和は200000以下」と書かれているので、right = infではなく、その値を入れることでシミュレート可能になる

学び

  • 二分探索の上限を適切に決めると、判定にシミュレーションが使える