資源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に割り当てる。
- 葉ならB_0,B_1をdのコピーとする。葉でなければ
(B_0,B_1)←dfs(h,d)とする。 - 各light child uについて、
B_0←dfs(u,B_0)_0とB_1←dfs(u,B_1)_1を別々に評価する。途中の二入力は異なるので、この二回は共有できない。 - 子を反映した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公式解説がこの評価順の適用例である。
問題一覧
- ABC311 Ex「Many Illumination Plans」 公式問題組合せ: 資源・容量DP
技能・出典
主題: 資源DPを引数で渡すHLRecDP(外部の資源DP配列を受け取って部分木の選択を反映する再帰を設計し、max-plusの子DP併合を避ける。重い子は一回だけ呼び、軽い子の重複呼出しを部分木サイズの半減により評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 資源DPを引数で渡すHLRecDP / 補助タグ: 資源軸knapsack DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 赤色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。