ABC 289 G — Shopping in AtCoder store

考察

customer motivationをB_1≥…≥B_Nにsortすると、ちょうど上位i人が買う最適price候補はB_i+C_jであり、売上はi(B_i+C_j)になる。

各item値x=C_jの答えはf(x)=max_{1≤i≤N}{i·x+iB_i}で、傾きi・切片iB_iの直線群の上側包絡線queryに一致する。

傾きはi=1..Nで単調増加し、全query xも事前に分かるのでstatic Convex Hull Trickを使える。

採用する候補: 傾き順に直線をupper hullへ追加し、各C_jで最大値をqueryするConvex Hull Trick。

N×Mの候補評価を、不要直線の除去と包絡線上の探索へ圧縮できる。

棄却する候補: itemごとにi=1..Nを全走査してi(B_i+C_j)の最大を取る。

N,Mとも2×10^5で積が大きすぎる。

棄却する候補: motivation最大のcustomerに合わせたprice B_1+C_jだけを選ぶ。

priceを下げて購入人数を増やす方が売上が大きい場合があり、iのtrade-offを無視する。

買う人数が変わらないprice区間ではpriceを上端まで上げられるため、候補priceを各customerの購買限界B_i+C_jへ離散化できる。

直線の傾きが追加順に増えるので、新直線との交点が前の有効開始点以前なら末尾直線をpopするstack型hullを作れる。

Bを降順sortし、i=1..Nについてline y=i·x+iB_iを傾き順に追加する。末尾2本と新線の交点順が非増加なら中央線を削除し、各線が最大になるx区間の左端を保持する。各C_jでは左端をbinary searchして該当lineを選び、i(C_j+B_i)を64bitで評価して入力順に出力する。queryをC順にsortしてpointer走査する実装でもよい。

典型の発動条件

Convex Hull Trick

発動条件: max/min of affine functionsを多数のxで求めるとき。

売上候補を直線へ変換し、upper envelopeだけを保持する。

候補priceの閾値化

発動条件: 需要がpriceのthresholdで段階的に変わる収益最大化。

需要人数が変わる購買限界までpriceを上げ、人数iごとに1候補へする。

単調傾きのstack hull

発動条件: 直線をslope順に追加できるstatic CHT。

交点順が壊れる末尾線をpopする。

問題固有の要素

itemごとの差はx=C_jというquery座標だけで、customer側の直線群は全itemに共通するため、一度作った包絡線をM回再利用できる。

別の問題へ持ち帰る視点: 多数のparameter付き最適化では、候補をparameterのaffine関数へ書き、共通envelopeとqueryに分離する。

正当性

B降順で買う人数が一定なprice区間では上端B_i+Cへ上げても人数を減らさず売上を増やす。従って最大売上はmax_i i(C+B_i)。これを傾きiの直線へ写した上側包絡線は全候補の最大値と同じで、cross積による無効線除去はどのxでも最大にならない線だけを落とす。query位置の有効線を選べば最適値になる。

実装上の注意

  • 交点比較は除算せずcross multiplicationし、積が64bit範囲を越え得る中間では128bit整数を使う。
  • 売上自体も最大約4×10^14なので64bit整数で出力する。
  • 同じ有効開始点や境界xではどちらのlineを選んでも最大値になるよう、pop・binary searchの不等号を統一する。

復習の核

  • Bを降順にした小例でiごとの直線を描き、途中で一度も最大にならない線がpopされることと、交点ちょうどのCで売上が一致することを確認する。

計算量と制約

時間

O(N log N+M log N)。B sort、単調傾きhull、二分query。

空間

O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq2\times10^5; 1\leq M\leq2\times10^5; 0\leq B _ i\leq10^9\quad(1\leq i\leq N); 0\leq C _ i\leq10^9\quad(1\leq i\leq M); All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Shopping in AtCoder store の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Convex Hull Trick・直線包絡

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Convex Hull Trick・直線包絡

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

      学習の位置

      体系上の位置: Convex Hull Trick・直線包絡

      • 一次関数候補の傾き・交点順を保ち、query点で包絡線上の最適な直線を選べる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題