分離凸・凹の単調限界値選択

概要

資源を一単位ずつ配るときの費用が、同じ対象へ配るほど高くなるなら、各対象の「次の一単位」を比べればよい。必要量が少なければ優先度付きキューで一つずつ選び、巨大なら費用の閾値でまとめて数える。利益最大化では、限界利益が非増加になる場合を同じように扱う。

考え方

一次元凸・単峰最適化では、一つの変数を増やしたときの差分を調べた。ここでは複数の整数変数 x1,…,xNx_1,\ldots,x_N に合計 KK 単位の資源を配り、総費用 ∑i=1Nfi(xi)\sum_{i=1}^N f_i(x_i) を最小化する。各変数の費用がその変数だけで決まることを「分離可能」という。総和と各変数の上下限以外の制約は、まず置かない。

二つの増分列を併合する

説明用の小例として、x12+2x22x_1^2+2x_2^2 を、x1+x2=3x_1+x_2=3、x1,x2≥0x_1,x_2\geq 0 の下で最小化する。両方を0から始めると、各変数を一つ増やす費用は

Δ1(x)=2x+1,Δ2(x)=4x+2\Delta_1(x)=2x+1,\qquad \Delta_2(x)=4x+2

なので、それぞれ (1,3,5,…)(1,3,5,\ldots) と (2,6,10,…)(2,6,10,\ldots) になる。一つの列の途中だけを選ぶことはできず、例えば費用3を払うには、その前の費用1も払う必要がある。

各列の未選択部分の先頭を比べ、安い方の対象へ1単位だけ追加し、その限界費用を払う。「次の費用」の組は対象1、対象2の順で示す。

次の費用操作配分後総費用
(1,2)(1,2)対象1へ1単位(費用1)(1,0)(1,0)1
(3,2)(3,2)対象2へ1単位(費用2)(1,1)(1,1)3
(3,6)(3,6)対象1へ1単位(費用3)(2,1)(2,1)6

各操作で支払った限界費用は1、2、3であり、配分 (2,1)(2,1) の費用は 22+2×12=62^2+2\times 1^2=6 となる。残りの配分 (0,3),(1,2),(3,0)(0,3),(1,2),(3,0) の費用は18、9、9なので、確かに最小である。

一般には整数の下限 lil_i、上限 uiu_i(li≤uil_i\leq u_i)を置き、xi=lix_i=l_i から始める。追加で配る量は M=K−∑iliM=K-\sum_i l_i、初期費用は ∑ifi(li)\sum_i f_i(l_i) である。各 ii の未選択部分の先頭、すなわち xi<uix_i<u_i のときの Δi(xi)=fi(xi+1)−fi(xi)\Delta_i(x_i)=f_i(x_i+1)-f_i(x_i) と対象番号を最小ヒープに入れる。最小費用を取り出して対応する変数を一つ増やし、上限に達していなければその列の次の費用を入れる。これを MM 回繰り返す。

この手順が安全なのは、各列の差分が非減少だからである。列の奥に先頭より安い費用は隠れていないので、ヒープの最小値は全未選択増分の最小値でもある。従って毎回最小値を選ぶと、全列を合わせた中で小さい方から MM 個を、各列の先頭から連続する形で選べる。任意の可解な配分も同じ初期状態に MM 個の増分を足したものだから、それより安い総費用にはならない。同じ費用ならどの列を先に選んでもよい。

閾値で個数と総和をまとめる

MM が巨大なときは、一単位ごとの操作を避ける。各列について、費用が閾値 λ\lambda 以下である増分の個数を ci(λ)c_i(\lambda)、その総和を si(λ)s_i(\lambda) とする。個数の和は閾値に対して非減少なので、M>0M>0 なら ∑ici(λ)≥M\sum_i c_i(\lambda)\geq M となる最小の閾値を二分探索する。以下では増分が整数の場合を考える。

先ほどの二次費用を fi(x)=aix2f_i(x)=a_i x^2、下限を0と書けば、増分は ai(2x+1)a_i(2x+1) である。正の整数 aia_i と整数閾値 λ\lambda に対し、個数と総和は

ci(λ)=max⁡(0,⌊λ+ai2ai⌋),si(λ)=aici(λ)2\begin{aligned} c_i(\lambda)&=\max\left(0,\left\lfloor\frac{\lambda+a_i}{2a_i}\right\rfloor\right),\\ s_i(\lambda)&=a_i c_i(\lambda)^2 \end{aligned}

となる。上限 uiu_i があれば個数を uiu_i 以下に切り詰める。総和の式は、先頭から cic_i 個の差額の和が fi(ci)−fi(0)f_i(c_i)-f_i(0) になることから分かる。

a1=1,a2=2,M=3a_1=1,a_2=2,M=3 では、閾値2の個数は (1,1)(1,1) で合計2、閾値3では (2,1)(2,1) で合計3になる。従って境界は λ=3\lambda=3 であり、総和も 1×22+2×12=61\times 2^2+2\times 1^2=6 と求まる。

同値が複数あると、境界以下をすべて採るだけでは個数を超える。例えば両方の費用を xi2x_i^2 に変えると、列はともに (1,3,5,…)(1,3,5,\ldots) になる。3個選ぶ境界はやはり3だが、3以下には合計4個ある。まず3未満の増分(費用1)を両列から一つずつ採り、残り1個だけを費用3の候補へ配る。配分は (2,1)(2,1) または (1,2)(1,2)、費用は 1+1+3=51+1+3=5 である。

一般にも、境界未満の個数 C<C_{<} と総和 S<S_{<} を求め、追加費用を

S<+(M−C<)λS_{<}+(M-C_{<})\lambda

とする。整数増分なら C<=∑ici(λ−1)C_{<}=\sum_i c_i(\lambda-1)、S<=∑isi(λ−1)S_{<}=\sum_i s_i(\lambda-1) である。配分も必要なら、各列に境界未満の個数を配った後、各列の ci(λ)−ci(λ−1)c_i(\lambda)-c_i(\lambda-1) 個までを使って残数を配る。一つの列で同値が続く場合も、先頭から順に採る。初期費用は別に足す。

探索範囲も増分列から決める。各列から使うのは高々 MM 個なので、上限を一時的に min⁡(ui,li+M)\min(u_i,l_i+M) へ切り詰めてよい。空でない列の先頭の最小費用から、末尾の最大費用までを整数閾値の探索範囲にする。後者以下には配るのに十分な個数がある。二次費用で下限が0なら、上端は例えば max⁡iai(2M−1)\max_i a_i(2M-1) と置ける。

下限が0でない場合は、数える増分の添字を li≤x<uil_i\leq x<u_i に限定する。M=0M=0 なら探索せず初期配分を返す。可解条件は ∑ili≤K≤∑iui\sum_i l_i\leq K\leq\sum_i u_i であり、上限に達した列の次費用は候補へ入れない。

次数配分へ帰着できる理由を確かめる

ABC359 F「Tree Degree Optimization」の解説では、頂点 ii の次数を did_i とすると、費用が ∑iAidi2\sum_i A_i d_i^2 となる。頂点数 N≥2N\geq 2 の木の次数列は、di≥1d_i\geq 1 と ∑idi=2N−2\sum_i d_i=2N-2 を満たす任意の整数列として実現できる。ここが、木の辺の選び方を資源配分へ置き換えられる根拠である。

従って全次数を1から始め、残る N−2N-2 単位を配る。一回の増分は Ai(2di+1)A_i(2d_i+1) で、最初の候補は 3Ai3A_i となる。小例の下限0との違いを意識して読むとよい。単に「木の問題でも安い増分を選ぶ」と覚えず、次数列の条件が十分であることを先に確かめる。

本数別の凹性を交換構造から証明する

選ぶ個数 kk ごとの最適利益を FkF_k とする。利益の差分が非増加なら、大きい増分から併合できる。ただし、まず FkF_k が凹である根拠を確認する。二次式の差分が非増加、木DPの初回の加算利益が非負など、遷移から直接帰納できる場合がある。最適列を複数の候補列の点ごとの最大値で作る場合、子列が凹であることだけでは親の凹性は保証されない。例えば (0,4,4,4)(0,4,4,4) と (0,2,4,6)(0,2,4,6) の点ごとの最大値は (0,4,4,6)(0,4,4,6) で、差分4、0、2が非増加を満たさない。

排他制約がある場合は、k−1k-1 個と k+1k+1 個の最適解を二色で重ね、総利益を保存して kk 個ずつへ再分配できないか考える。それが可能なら、二つの kk 個解の値はそれぞれ FkF_k 以下なので

2Fk≥Fk−1+Fk+12F_k\geq F_{k-1}+F_{k+1}

となる。等長区間の選択では、各色の解の中で区間同士が重ならないため、各区間が他色と高々二つしか衝突しない。二部の衝突グラフは道・偶閉路・孤立点へ分かれ、一本多い色の成分を交換できる。マッチングも交互路の辺の色交換で同じ証明になる。

この議論は許可候補を固定した各境界状態でも成立する。異なる長さの区間など、一つの候補が他色の三つ以上と衝突する場合は別の証明が必要である。ちょうど指定個数を選ぶ最適列は、利益が負でも全実現可能個数まで保持する。個数が上限以下でよい問題なら、非正の限界利益を追加する義務はない。

ここでの交換による凹性の証明は、候補間に排他制約がある問題を、制約込みの最適値列へ要約するための議論である。元の候補をそのまま増分と見なして、先ほどの単純な貪欲法へ項間制約を追加してよいという意味ではない。

成立条件と計算量

NN 列から追加で MM 個選ぶとき、初期ヒープを線形時間で構築すれば、時間は O(N+Mlog⁡(N+1))O(N+M\log(N+1))、追加空間は O(N)O(N) である。これは一回の増分評価が O(1)O(1) の場合であり、選んだ全増分を保存する必要はない。

閾値探索では、答えを含む整数閾値の範囲を導く。候補値の幅を WW とし、各列の個数を O(1)O(1) で数えられれば、二分探索と最後の総和・配分復元は O(N(1+log⁡(W+1)))O(N(1+\log(W+1))) 時間となる。入力と配分を保持する空間は O(N)O(N) である。個数や総和に別の計算が必要なら、その費用を加える。個数だけ速く数えられても、費用を求めるには総和の計算方法が必要になる。積・総和の整数幅と、同値費用の残数配分にも注意する。

成立条件は、費用が変数ごとの和に分離できること、各列の差分が非減少であること、制約が総資源量と各変数の整数上下限だけであること。負の増分も、合計をちょうど満たす問題なら同じ順序で扱える。利益最大化では各列の差分が非増加であることを示し、最大ヒープや閾値以上の個数・総和へ向きを反転する。項間の追加制約があれば、そのままの貪欲選択を使わず、制約を満たす交換や別の最適化構造を証明する。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。単調な限界費用の列を導き、heapや閾値計数で必要個数を選ぶ。

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

概念上の親: 凸性・傾き・限界費用・slope trick。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-separable-convex-marginals

分離凸・凹の単調限界値選択

習得する技能

  • 分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。

前提と範囲

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

直接の前提単元: 一次元凸・単峰最適化。

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

離散凸・凹の差分が単調になることを確認し、複数の限界値列から必要な上位・下位K項だけをheap mergeまたは閾値計数で選ぶ。

このUnitでは扱わないもの

  • 分離凸・凹の単調限界値選択の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠