資源DPを引数で渡すHLRecDP

概要

外部の資源DP配列を受け取って部分木の選択を反映する再帰を設計し、max-plusの子DP併合を避ける。重い子は一回だけ呼び、軽い子の重複呼出しを部分木サイズの半減により評価する。

dfs(v,dp)の引数は外部で既に選んだ候補の資源別最適値であり、返値は部分木vの選択肢も反映した値と定義する。独立な二配列のmax-plus mergeを、選択・非選択のO(X)更新へ展開する。重い子を一回だけ通す評価順を先に導く。

軽い子が半分以下というだけでO(NX log N)にはならない。各軽い子を二回呼ぶABC311 Exでは、サイズnの再帰量に重い子の一回分と軽い子の二回分が加わり、均等二分時は3T(n/2)となる。全heavy path根からの処理も含めO(N^(log₂3)X)を評価する。畳み込みを使う木DPとは別の証明である。

考え方

二状態の木上knapsackを標準形にする。頂点vは費用w_v、利益b_v、色c_v∈{0,1}を持つ。状態sでは、部分木内で最初に選ぶ頂点の色をsに制限する。vを選ばなければ各子も状態s、vを選ぶならs=c_vであり、子へは反対色1-sを要求する。費用は容量K以下とする。

外部配列から二つの返値を定義する

入力d[t]は、部分木vの外部で既に使った費用がちょうどtである最適利益。実現不能は−∞とする。dfs(v,d) の返値R_s[t]は、その外部選択へ、部分木vの状態sに従う選択を追加した最適利益である。部分木だけのDPではない。

子だけを合成した配列をB_0,B_1とすると、vを選ばない候補は R_s[t]=B_s[t]。選ぶ候補は R_{c_v}[t+w_v]=max(R_{c_v}[t+w_v],B_{1-c_v}[t]+b_v)(t+w_v≤K)である。Bの値を読み終えるまで書き換えず、vを一回だけ選ぶ。w_v=0でも別配列から読むので重複更新しない。

各子の二つの独立した資源配列をmax-plus畳み込みする代わりに、既存の配列をその子のdfsへ渡す。すなわちB_sへ子uを反映する操作は B_s←dfs(u,B_s)_s となる。外部で使った費用が入力に載っているので、子の選択追加はO(K)の頂点更新へ展開できる。

heavy childの一回を共有する評価順

子を処理する前はB_0=B_1=dである。したがって最初の子は dfs(h,d) を一回呼ぶだけで両状態の結果を同時に得られる。これを部分木サイズ最大のheavy child hに割り当てる。

  1. 葉ならB_0,B_1をdのコピーとする。葉でなければ (B_0,B_1)←dfs(h,d) とする。
  2. 各light child uについて、B_0←dfs(u,B_0)_0 と B_1←dfs(u,B_1)_1 を別々に評価する。途中の二入力は異なるので、この二回は共有できない。
  3. 子を反映したB_0,B_1を保存し、上記の費用シフトでvの選択を追加してR_0,R_1を返す。

各子の処理後に「既に処理した子で許される選択を、外部配列へすべて追加している」という不変量を持つ。帰納的にdfsは正しく、根へd[0]=0、d[t>0]=−∞を渡せば答えを得る。max-plus畳み込みを一度も実行しない点が核心である。

成立条件と計算量

子サイズをn_1≥n_2≥…とすると、呼出しの仕事量は T(n)≤T(n_1)+2Σ_{i≥2}T(n_i)+O(K)、Σ n_i=n-1。配列は所有権を移して渡し、子ごとの不要なO(K)コピーを避ける。

α=log₂3と置く。非最大の子をまとめて評価すると、n_1^α+2Σ_{i≥2}n_i^α≤(n-1)^α となる。これは、非最大側をまとめられる範囲ではまとめて最大化し、二分の比率t≤1/2に対して (1-t)^α+2t^α≤1(凸関数なので区間の端点t=0,1/2で上界を得る)を用いて示せる。これを再帰に代入し、頂点のO(K)仕事も含めて T(N)=O(N^α K) を得る。均等二分木ではheavy一回・light二回の 3T(N/2) がこの指数を示す。

同じ外部初期配列で全ての部分木の答えが必要なら、heavy path先頭だけから呼ぶ。heavy先行の入力は変わらないので、そのpath上の各dfsが各部分木の初期配列からの答えも得る。light深さdが同じpath先頭の部分木は互いに素で、サイズ総和はN以下、個々のサイズはN/2^d以下。したがってサイズのα乗の和は N^α / 2^{d(α-1)} 以下で、dについて合計してO(N^α)。全体の上界を保てる。

heavy処理は末尾呼出しに近い形で先行させ、配列を再利用し、light再帰でだけ親の配列を保存すれば作業配列はO(K log N)。二状態の遷移数が増える別のDPには、呼出し係数を再評価する必要がある。ABC311 Ex公式解説がこの評価順の適用例である。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 赤色(2800以上)。資源DPを再帰の引数にし、軽い子への重複呼出しまで含めて計算量を証明する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-heavy-light-recursive-dp

資源DPを引数で渡すHLRecDP

習得する技能

  • 外部の資源DP配列を受け取って部分木の選択を反映する再帰を設計し、max-plusの子DP併合を避ける。重い子は一回だけ呼び、軽い子の重複呼出しを部分木サイズの半減により評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 資源・容量DP、根付き木DP・部分木集約。

このUnitを直接前提とする単元: なし。

資源軸knapsack DP・根付き木DP・部分木集約で得た考え方と実装を再利用し、資源DPを引数で渡すHLRecDPの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 資源DPを引数で渡すHLRecDPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠