ABC 389 E — Square Price

考察

商品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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Square Price の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 分離凸・凹の単調限界値選択

主題
  • 分離凸・凹の単調限界値選択: 分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 分離凸・凹の単調限界値選択

    補助タグ: 単調境界探索

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 分離凸・凹の単調限界値選択

    • 分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。

    先に読む単元:

    • 一次元凸・単峰最適化 — 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 単調境界を証明して探索する — 判定結果が一方向に変わることを証明し、巨大な値域から成功・失敗の境界を二分探索で求める。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題