考察
商品iをk個買うcost k²P_iは、限界価格P_i,3P_i,5P_i,…の安い順にk個買う総和と等しい。全商品を跨いで限界価格の安いものから取るgreedyに言い換えられる。
限界価格x以下を全て買う個数とcostは、各iでk_i=floor((x/P_i+1)/2)としてΣk_i, ΣP_i k_i²からO(N)で評価できる。
採用する候補: 買える限界価格thresholdを二分探索し、残予算で境界価格の商品を追加する
threshold以下の総costは単調で、O(N log M)で最大thresholdを求めた後、次の同価格限界単位を残予算分だけ加えれば最適個数になる。
棄却する候補: 各商品の次の限界価格をheapで一個ずつ取り出す
答え個数が予算Mに比例して最大10^18級になり得て、購入単位ごとのloopは終わらない。
平方costの差(k+1)²-k²=2k+1が限界価格列を作る。
threshold計算中はcostがMを超えた時点で打ち切り、積P_i k_i²のoverflowを防ぐ。
xを限界価格としてtotalCost(x)=ΣP_i floor((x/P_i+1)/2)²≤Mの最大xを二分探索する。対応個数cntと残金を求め、価格x+1の限界単位を買えるだけ追加する。
典型の発動条件
凸costの限界費用展開
発動条件: 同種をk個取るcostが離散凸で、総個数を予算内最大化するとき。
差分costを独立unitの価格とみなして全体greedyにする。
answer thresholdの二分探索
発動条件: 閾値以下の全候補の個数・総costを集約できるとき。
購入境界の限界価格を単調判定する。
問題固有の要素
各種類の平方costをそのまま最適化せず、離散微分すると全種類共通の「最安から購入」という単純greedyになる。
別の問題へ持ち帰る視点: separable convex resource allocationは各変数のmarginal cost列をmergeする視点を持つ。
正当性
商品iのk個costは増加限界価格P_i,3P_i,…のprefix和。全限界単位を安い順に買うとprefix条件が自動的に守られ、同個数の最小costを与える。threshold以下全購入costが予算内となる最大整数xを選ぶと、次価格x+1全ては買えない。残金でその同価格単位だけ追加した後はどの安い単位も残っておらず個数最大になる。
実装上の注意
- upper boundとmid計算、P_i k_i²には128 bit相当を使いM超過でsaturateする。境界価格の追加数を実在する次unit数で制限する。
復習の核
- N≤5,M≤1000でheapによるunit greedyと比較し、thresholdに価格が存在しない場合、同価格unit多数、P_i>Mを確認する。
計算量と制約
時間
O(N log M)。価格thresholdごとの平方cost評価。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^{5}; 1 \leq M \leq 10^{18}; 1 \leq P_i \leq 2 \times 10^{9}; All input values are integers.
出典