資源・容量DP
概要
資源軸knapsack DP
容量・時間・個数などの有界資源を軸に選択の価値を更新する。
考え方
処理済みの品物数と使用資源量を状態にする。各品物を高々一度使うなら、同じ品物の遷移結果を入力に再利用しないよう配列を分けるか容量を降順に更新する。
価値最大化で「重さちょうどt」を表すならdp[0]=0、t>0は−∞とする。0/1品物(w,v)はtを容量Kからwへ降順に dp[t]=max(dp[t],dp[t−w]+v) と更新する。入力側t−wを今の品物で更新する前に読むので一回しか使わない。無制限品物でw>0なら逆に昇順で更新し、その品物を繰り返し使った状態から延長する。上限Kなら最後にmax_{t≤K}dp[t]、ちょうどKならdp[K]を返す。
無制限の重さ0で正価値なら上へ非有界。有限個の0/1品物で重さ0なら、別配列から一回だけ遷移する方法が定義を保つ。個数を数える場合は、品物種を外ループにする組合せと、容量を外ループにする順序付き列を区別する。
成立条件と計算量
N品物・容量K・定数遷移ならO(NK)。これはKの値に比例する擬多項式であり、巨大なKには使えない。重さ0、到達不能の番兵、負の評価、ちょうどKと高々Kの違いを固定する。
問題一覧
- ABC410 E「Battles in a Row」 公式問題
- ABC322 E「Product Development」 公式問題組合せ: 最小十分状態からDPを設計する
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: 資源軸knapsack DP / 補助タグ: DPの最小十分状態
- ABC390 E「Vitamin Balance」 公式問題組合せ: 交換論から選択順を導く
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 貪欲法と交換論
- ABC419 E「Subarray Sum Divisibility」 公式問題
- ABC441 F「Must Buy」 公式問題
- ABC364 E「Maximum Glutton」 公式問題
- ABC222 E「Red and Blue Tree」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 寄与の数え上げと順序交換
- ABC216 F「Max Sum Counting」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 寄与の数え上げと順序交換
- ABC341 F「Breakdown」 公式問題
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 資源軸knapsack DP / 補助タグ: DAGのtopological processing
- ABC275 F「Erase Subarrays」 公式問題
- ABC321 F「#(subset sum = K) with Add and Erase」 公式問題
- ABC383 F「Diversity」 公式問題
- ABC325 F「Sensor Optimization Dilemma」 公式問題
- ABC461 F「Total Product is N」 公式問題組合せ: 素因数分解と約数構造
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 素因数・約数分解
- ABC288 E「Wish List」 公式問題
- ABC320 F「Fuel Round Trip」 公式問題
- ABC307 G「Approximate Equalization」 公式問題
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 累積和・差分配列
- ABC269 G「Reversible Cards 2」 公式問題
- ABC424 G「Set list」 公式問題
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。)。主タグ: 資源軸knapsack DP / 補助タグ: 二部matching・Hall・Kőnig
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC287 F「Components」 公式問題主題: 根付き木DP・部分木集約
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 資源軸knapsack DP
- ABC290 Ex「Bow Meow Optimization」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 貪欲法と交換論 / 補助タグ: 資源軸knapsack DP
- ABC310 Ex「Negative Cost」 公式問題
技能・出典
主題: 大容量unbounded knapsackのeventual linearity(剰余の鳩の巣原理と密度交換で非基準itemの使用量を界し、有限prefix DPと最大密度itemの反復から巨大capacityの最適値を求められる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 大容量unbounded knapsackのeventual linearity / 補助タグ: 資源軸knapsack DP
- ABC311 Ex「Many Illumination Plans」 公式問題
技能・出典
主題: 資源DPを引数で渡すHLRecDP(外部の資源DP配列を受け取って部分木の選択を反映する再帰を設計し、max-plusの子DP併合を避ける。重い子は一回だけ呼び、軽い子の重複呼出しを部分木サイズの半減により評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 資源DPを引数で渡すHLRecDP / 補助タグ: 資源軸knapsack DP
- ABC332 G「Not Too Many Balls」 公式問題主題: 最大流・最小カット
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 最大流・最小カット / 補助タグ: event・値順のオフライン走査、資源軸knapsack DP
- ABC366 F「Maximum Composition」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 貪欲法と交換論 / 補助タグ: 資源軸knapsack DP
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。) / priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 貪欲法と交換論、資源軸knapsack DP、priority queue・best-first列挙
- ABC375 E「3 Team Division」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: DPの最小十分状態 / 補助タグ: 資源軸knapsack DP
- ABC382 E「Expansion Packs」 公式問題主題: 確率過程・期待値DP
技能・出典
主題: 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 確率・期待値DP / 補助タグ: 資源軸knapsack DP
- ABC416 F「Paint Tree 2」 公式問題主題: 根付き木DP・部分木集約
技能・出典
主題: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 根付き木DP・部分木集約 / 補助タグ: 資源軸knapsack DP
- ABC426 G「Range Knapsack Query」 公式問題主題: 再帰分割・分割統治
技能・出典
主題: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 再帰分割・分割統治 / 補助タグ: 資源軸knapsack DP
- ABC428 G「Necklace」 公式問題主題: 群作用・軌道数え上げ
技能・出典
主題: 群作用・軌道数え上げ(群作用の固定点数を群要素のcycle typeごとに数え、BurnsideまたはPólyaの平均でorbit数を求められる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 群作用・軌道数え上げ / 補助タグ: 資源軸knapsack DP、法上の四則演算・高速累乗・逆元、素因数・約数分解
前提・学習成果・出典
習得対象の目安: 緑色(800–1199)。個数・容量を軸とするナップサック型DPを実装し、更新方向を説明する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-subset-resource
習得する技能
- 資源軸の上限と更新順を選び、選択の重複を避けられる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: 大容量unbounded knapsackのeventual linearity、資源DPを引数で渡すHLRecDP。
最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。
このUnitでは扱わないもの
- 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。