ABC 426 G — Range Knapsack Query

考察

各クエリは部分配列 [L,R] 内の 0/1 ナップサックで、容量 C は小さい。区間ごとに DP を作ると重複が大きいが、分割点をまたぐクエリは左右の DP を合成できる。

採用する候補: 配列を分割統治し、各節点で中央をまたぐ全クエリへ左 suffix DP と右 prefix DP を構築して答える。

各要素は深さごとに一度 DP 更新へ寄与し、各クエリも一節点で処理されるため O(K(N log N+Q)) になる。

棄却する候補: クエリごとに [L,R] の全アイテムでナップサック DP をやり直す。

区間の重複を共有できず O(NKQ) に達する。

区間 [l,r] の中央 m に対し、L<m≤R のクエリだけをこの節点で処理し、片側に収まるものは再帰へ送る。

容量 j を左に、C-j を右に配る全分割を試せば、左右で独立に選んだ最適値の和が区間全体の最適値になる。

solve(l,r) で m を定め、i=m-1…l の suffix ナップサック dp_l[i][j] と i=m…r の prefix ナップサック dp_r[i][j] を容量 K まで作る。中央をまたぐ各クエリを max_j(dp_l[L][j]+dp_r[R][C-j]) で答え、残りを左右へ再帰する。

空の品物集合の「容量j以下」DPは全jで0に初期化する。品物追加は容量降順でdp[j]=max(dp[j],dp[j−W]+V)。再帰の葉l=rでは、その一品だけを見てW_l≤CならV_l、そうでなければ0と答える。これでL=Rのqueryも必ず処理される。

典型の発動条件

オフライン区間分割統治

発動条件: 静的配列上の多数の区間クエリを、中央をまたぐものと片側のものへ分類できるとき。

各クエリを両端が初めて分かれる節点で一度だけ処理する。

prefix・suffix ナップサック DP

発動条件: 区間が固定境界をまたぎ、左右の選択が容量配分だけで結合するとき。

中央から外向きにアイテムを追加した DP を全端点分共有する。

問題固有の要素

クエリ区間そのものではなく、再帰木で両端が分離する唯一の節点を担当箇所にすると DP の再利用範囲が最大化する。

別の問題へ持ち帰る視点: 結合条件が小さい容量だけなら、左右の区間情報を容量配分の max-plus 畳み込みで合成できる。

正当性

各照会は両端が初めて左右に分かれる節点、または一要素の葉で一度だけ処理される。交差区間の任意の選択は左右の選択に分かれ、容量配分のどれかで必ず表せる。逆に左右のDPの合成は合法な選択なので、その最大が区間の最適値になる。

実装上の注意

  • 左 DP は m-1 から降順、右 DP は m から昇順にコピー更新する。容量以下の最大値として j=0 を 0 に初期化し、到達不能値の扱いを統一する。

復習の核

  • 中央をまたぐ条件を L<m≤R と統一し、各クエリがちょうど一つの再帰節点で回答されることを確認する。

計算量と制約

時間

O(NK log N+QK)、N品数K最大容量Q区間query。

空間

O(NK+Q)、親配列を解放してから子へ再帰する。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 2\times 10^4; 1\leq Q \leq 2\times 10^5; 1\leq W_i \leq 500; 1\leq V_i \leq 10^9; 1\leq L_j \leq R_j \leq N; 1\leq C_j \leq 500; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Range Knapsack Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 再帰分割・分割統治

主題
  • 再帰分割・分割統治: pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。
追加で学ぶ技能
    なし
    既習技能
    • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。

    主タグ: 再帰分割・分割統治

    補助タグ: 資源軸knapsack DP

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

    学習の位置

    体系上の位置: 再帰分割・分割統治

    • pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。

    先に読む単元:

    • 資源・容量DP — 最小十分状態を設計できるようになった後、選択数・容量・費用などの資源軸で遷移を表し、0/1選択と無制限選択の更新方向を区別する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題