ABC 216 F — Max Sum Counting

考察

条件 max A_i ≥ sum B_i は、選んだ集合の中で最大の A を持つ要素を一つ固定すると、残りの B の総和上限として表せる。組 (A_i,B_i) を A_i の昇順に並べれば、各非空部分集合にはソート順で最後に選ばれた一意な要素 i がある。最大値という集合全体の条件を、最大を担当する一要素 i の固定へ変えると、残りは加法的な B のナップサック条件になる。A が同値の要素が複数あっても、ソート後に最後に選んだ添字を証人にすれば各部分集合はちょうど一度だけ数えられる。

棄却する候補: 全ての部分集合を列挙し、それぞれで A の最大値と B の合計を計算して条件を確認する。

N 個の要素の部分集合は 2 の N 乗個あり、N=5000 では列挙できない。

採用する候補: A の昇順に各要素を最大値の証人として固定し、それ以前の要素から B 和が A_i−B_i 以下となる選び方を部分和 DP で数える。

全ての非空部分集合を最後の要素で重複なく分類でき、以前の要素の情報は B の総和別個数だけで十分になる。

A 順の最後の選択要素で部分集合を分割し、走査済み要素の B 和別選択数を 0/1 ナップサック DP として維持して閾値以下を加算する。

典型の発動条件

極値を担当する証人の固定

発動条件: 部分集合条件に最大値または最小値が現れ、各集合を一意な極値要素で分類できるとき。

A でソートし、最後に選んだ i を最大 A の担当として、残りの選択を以前の要素だけへ限定する。

部分和の 0/1 ナップサック数え上げ

発動条件: 各要素を高々一度選び、重み総和別の部分集合数を逐次維持するとき。

走査済み要素の B 和 s ごとの個数を持ち、i を証人にする前に s≤A_i−B_i の個数を答えへ足す。

問題固有の要素

証人 i 自身の B_i も総和へ含まれるため、以前の要素へ許される上限は A_i ではなく A_i−B_i になる。

別の問題へ持ち帰る視点: 極値要素を固定して残りを DP するときは、証人自身が加法条件へ寄与する分を先に差し引く。

正当性

A順で各非空subsetを最後の選択要素iで分類する。この時max AはA_iであり条件は旧B和≤A_i−B_i。旧prefixの和DPを先に集計し後でiを追加すれば各subsetを一度だけ数える。同Aも固定したsort順で最後が一意。

実装上の注意

  • 要素 i の寄与を現在の DP から数えてから B_i を追加し、i を以前の要素として同じ寄与へ混ぜない。
  • A_i−B_i が負なら寄与は 0 とし、B 和の DP 更新は降順に行って同じ要素の複数回使用を防ぐ。

復習の核

  • max と総和が同じ不等式に現れたら、max を達成する要素を固定して残りへ許される総和を導く。
  • 極値が同値でも値だけで分類せず、ソート後の最後の添字という一意な証人を使って重複を避ける。

計算量と制約

時間

N要素、B和上限V=max A_i。sort O(N log N)、0/1 DP O(NV)。

空間

和別個数 O(V)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5000; 1 \leq A_i,B_i \leq 5000; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 資源軸knapsack DP

    補助タグ: 寄与の数え上げと順序交換

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

    学習の位置

    体系上の位置: 資源・容量DP

    • 資源軸の上限と更新順を選び、選択の重複を避けられる。

    先に読む単元:

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

    • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題