ABC 376 E — Max × Sum

考察

選ぶ K 個のうち A の最大値を与える index r を固定すると、A_r は定数になり、残り K-1 個はそれ以前の B が小さいものを選ぶだけでよい。

採用する候補: (A_i,B_i) を A 昇順に sort し、走査中にそれ以前の B の小さい K-1 個と総和を max-heap で維持して各 r を評価する。

棄却する候補: A が小さい K 個、または B が小さい K 個をそのまま選ぶ。

目的は max A と sum B の積であり、一方だけを局所最小化しても他方との trade-off を考慮できない。

A 昇順に並べ、heap が r より前の B の最小 K-1 個を表す時だけ A_r×(B_r+sumHeap) で答えを更新する。その後 B_r を heap へ入れサイズを K-1 に戻す。

典型の発動条件

最大要素の担当を固定

発動条件: 目的関数に選択集合の max と加法量の積が含まれるとき。

max を与える要素を走査し、残りを prefix 内の単純最適化へ落とす。

問題固有の要素

非線形な max×sum でも max の担当を決めれば残りは K-smallest の線形問題になる。

別の問題へ持ち帰る視点: ソート後の prefix 条件と heap の差分更新を組み合わせる定番形である。

正当性

r を選択集合中で A が最大の最後の index とすれば、候補は prefix r に限定され、A の値は A_r に固定される。 max-heap に K-1 個を保ち、新しい B を入れて最大を捨てると、各 prefix の最小 K-1 個の和が維持される。 最大 A の担当を全探索することで積の二要素を分離でき、各 prefix の K-1 最小和を差分更新して O(N log N) になる。

実装上の注意

  • 同じ A の順序は任意でも全候補を評価できる。heap に r 自身を入れる前に評価し、K=1 では空 heap を扱う。

復習の核

  • 集合中の最大 A を担う要素に印を付けた小例を作り、残りがなぜ B だけで選べるかを確認する。

計算量と制約

時間

O(N log N+N log K)、sortとK−1小値heap。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 2 \times 10^5; 1 \leq K \leq N \leq 2 \times 10^5; 1 \leq A_i, B_i \leq 10^6; The sum of N over all test cases is at most 2 \times 10^5.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Max × Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 貪欲法と交換論

    補助タグ: ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: 交換論から選択順を導く

    • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    先に読む単元:

    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

    • 対称操作による状態の正規化。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題