ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #560 F2. Microtransactions (hard version)

プログラミング競技プログラミング Codeforces

Problem - F2 - Codeforces

問題概要

※microtransactionは、オンラインゲームなどでのアイテム課金を指す言葉だそうです。文中では「アイテム」と訳します。

イヴァンはゲームのアイテムを買おうとしている。アイテムは $n$ 種類あり、種類 $i$ のアイテムは $k_{i}$ 個必要である。

イヴァンは毎日の朝に1円を稼ぎ、夜にアイテムを買う。アイテムは通常1個2円だが、「 $d_{j}$ 日目には、種類 $t_{j}$ のアイテムを1円で買える」というセール情報が合計で $m$ 個与えられる。

イヴァンは所持金が足りる限り1日にアイテムを好きなだけ買うことができる。イヴァンが全てのアイテムを必要数買い終わるまでの最小日数を求めよ。

制約

$1 \le n, m \le 2 \times 10^{5}$
$0 \le k_{i} \le 2 \times 10^{5}$
$1 \le \sum k_{i} \le 2 \times 10^{5}$
$1 \le d_{j} \le 2 \times 10^{5}$
$1 \le t_{j} \le n$

解法

この問題は、アイテムを全て買い終わる日を決めてしまうととても考えやすくなります。「アイテムを $X$ 日までに買い終わることは可能か？」という判定問題を考えて二分探索します。

アイテムの値段は全て同じなので、セールで買うアイテムの合計個数を最大化することを目指せばよいです。そしてアイテムは各日に好きなだけ買うことが可能なので、セールでの買い物は出来るだけ先延ばししたほうが使えるお金が多いので有利です。

そのため最適な戦略は

各アイテム種類ごとに、 $X$ 日までの間で一番最後のセール日しか買わないようにする。各アイテムごとに最後のセール日をリストアップしておく。
前からシミュレートする。基本はお金を貯めて、リストアップしたセール日が来たらそのアイテムを買えるだけ買う。
最終日に、セールで買えなかった不足分をまとめ買いする。

となります。買い終わる日を決めることで一番最後のセール日がいつなのかが分かり、最適な戦略が決まります。

二分探索の初期条件について考えましょう。 $S = \sum k_{i}$ とします。アイテムの合計必要個数×2のお金があればセールなしで全部買えるので $ok = 2S$ とできます。一方、全部セールで買ったとしても間に合わない条件を考えると $ng = S - 1$ とできます（適当に $ng = 0$ などでも問題ないです）。

二分探索のループが $O(\log S)$ 回実行され、それぞれの判定問題は実装によりますが $O(N+M)$ で可能なので、全体計算量は $O((N+M)\log S)$ となり間に合います。判定問題は各アイテムごとの最後のセール日を調べた後にソート等をするともう1つ $\log$ が付きますが、日数が少ないことを利用してバケットで管理すると線形時間になります。

ACコード

Submission #54115676 - Codeforces

少し前に二分探索の記事を書いたばかりだったので、タイムリーでした。