AtCoder 日立製作所社会システム事業部プログラミングコンテスト2020-D Manga Market

結構面白かったので、解説を。

解説

まず、 $a_i\neq 0$ のときは、経過時間が指数関数的に増加していくことに気がつく必要がある。これで、 $a_i\neq 0$ であるような店は高々 $O(log N)$ 個以内に収まることがわかる。

$a_i=0$ であるような店は、明らかに最後にまとめて訪れるのが良いので、 $a_i\neq 0$ の場合のみ考える。

連続してある2つの店を訪れる順番があったとして、それを入れ替えたほうがよい条件を考える。不等式を作って整理すると、

$a_{i+1}(b_i+1)\lt a_i(b_{i+1}+1)$

みたいな式が出てくる。結局これを不等号と定義して店を並べ替えれば、いつでも前から正しい順番で店を訪れることができるので、DPが使えるようになる。最後に $a_i=0$ であるような店を、累積和と二分探索で数えてくっつければOK。

解法の大筋はコンテストの後にTwitterで知っていたが、不等式処理と証明がしっかりできたのは嬉しかった。