ABC 348 G — Max (Sum - Max)

考察

選んだ要素の和は左右に分けて足せるが、そこから引く最大値は一度だけ数えたい。そこで、最大値がどちら側の選択で決まるかを固定する。BB の昇順に並べて区間を左右に分けると、両側から選ぶ場合の最大値は右側だけで決まる。左側では AA の和だけを最大化すればよくなり、右側には元と同じ形の部分問題が残る。

求めるのは、すべての選択数に対する

∑t∈SAt−max⁡t∈SBt\sum_{t\in S} A_t-\max_{t\in S} B_t

の最大値である。最大の BB を持つ要素を一つ固定すれば、残りは AA の大きいものから選べる。しかし、選択数と最大値の担当要素をそれぞれ列挙するだけで O(N2)O(N^2) 組あり、N≤2×105N\leq 2\times 10^5 には間に合わない。担当要素を一つずつ試す代わりに、左右のどちらにあるかでまとめるのが分割統治の狙いである。

区間の答えと一要素の基底

以後、要素の添字を0始まりとし、組 (At,Bt)(A_t,B_t) を BtB_t の昇順に並べる。solve(l,r) は、半開区間 [l,r)[l,r) からちょうど ii 個選ぶ最適値 fif_i を、0≤i≤r−l0\leq i\leq r-l について返す。

空集合には最大の BB が定義されないので、区間の答えでは常に f0=−∞f_0=-\infty とする。一要素なら返す配列は

(f0,f1)=(−∞,Al−Bl)(f_0,f_1)=(-\infty,A_l-B_l)

である。答えが負でも0に置き換えない。

区間が二要素以上なら m=⌊(l+r)/2⌋m=\lfloor(l+r)/2\rfloor で分け、左の長さを L=m−lL=m-l、右の長さを R=r−mR=r-m とする。左右を再帰して得た答えをそれぞれ uju_j、yky_k と書く。選び方は「左だけ」「右だけ」「両側から」の三つに分かれ、前二つは既に求まっている。残る両側からの選択を、左から選ぶ個数と右から選ぶ個数で合成する。

両側から選ぶ結合と有効な個数

左区間の AA を降順に並べた列を a1≥⋯≥aLa_1\geq\cdots\geq a_L とし、その累積和を

x0=0,xj=∑t=1jat(1≤j≤L)x_0=0,\qquad x_j=\sum_{t=1}^{j}a_t\quad(1\leq j\leq L)

と定める。xjx_j は左からちょうど jj 個選ぶときの、AA の和の最大値である。左区間の答え uju_j と異なり、BB は引いていない。

両側から選ぶときは、左で選んだどの BB も右で選んだ最大の BB 以下である。従って、左から jj 個、右から kk 個選ぶ最適値は xj+ykx_j+y_k となる。合計個数を i=j+ki=j+k とすると、両側から少なくとも1個ずつ選ぶ条件は

1≤i−k≤L,1≤k≤R1\leq i-k\leq L,\qquad 1\leq k\leq R

すなわち

max⁡(1,i−L)≤k≤min⁡(R,i−1)\max(1,i-L)\leq k\leq\min(R,i-1)

である。この有効列範囲で

zi=max⁡k(xi−k+yk)z_i=\max_k\bigl(x_{i-k}+y_k\bigr)

を求める。範囲が空なら zi=−∞z_i=-\infty とする。L,R≥1L,R\geq1 なので、両側から選べるのはちょうど 2≤i≤L+R2\leq i\leq L+R であり、i=0,1i=0,1 の行は探索しない。

最後に、各 1≤i≤L+R1\leq i\leq L+R で

fi=max⁡(ui,yi,zi)f_i=\max(u_i,y_i,z_i)

とする。i>Li>L の uiu_i、i>Ri>R の yiy_i は候補から除く。この解説では x0=0x_0=0 を累積和の初期値としてのみ使い、結合に j=0j=0 を含めない。右だけの選択は yiy_i で別に比較するため、三種類の選択が重ならない。

三要素で結合を追う

独自の小例として、既に BB 昇順に並んだ

(A,B)=(3,0),  (−2,1),  (4,2)(A,B)=(3,0),\;(-2,1),\;(4,2)

を考える。中央で分けると、左は最初の一要素、右は残りの二要素である。

左の答えは u=(−∞,3)u=(-\infty,3)、和の累積は x=(0,3)x=(0,3)。右では一要素の答えがそれぞれ −3-3 と 22 なので、1個選ぶ答えは2である。2個選ぶと −2+4−2=0-2+4-2=0 となり、右の答えは y=(−∞,2,0)y=(-\infty,2,0) になる。

両側から選ぶ場合、合計2個なら右選択数は k=1k=1、合計3個なら k=2k=2 だけが有効である。合計1個の両側選択は存在しない。次の表で、三種類の候補とその最大値を比較する。

ii左 uiu_i右 yiy_i両側 ziz_i答え fif_i
132−∞-\infty3
2なし03+2=53+2=55
3なしなし3+0=33+0=33

求める答えは (3,5,3)(3,5,3) となる。2個選ぶ最適集合では、負の A=−2A=-2 を避けて両側から1個ずつ選ぶ。3個なら負の要素も含める必要があるため、答えは小さくなる。選ぶ個数が増えれば答えも増える、とは限らない。

左の累積和の凹性から探索範囲を絞る

ここまでの式をすべての i,ki,k で直接計算すると、まだ二乗時間かかる。高速化の鍵は、左の累積和の差分が

xj−xj−1=ajx_j-x_{j-1}=a_j

であり、jj が増えるほど非増加になること、つまり xx が凹な列であることにある。右の答え yy に凹性は仮定しない。

行を合計個数 ii、列を右選択数 kk とする行列を、実際に全要素生成せず

M[i,k]=xi−k+ykM[i,k]=x_{i-k}+y_k

で評価する。隣接する二列がともに有効な範囲で、右の列へ移る利得は

M[i,k+1]−M[i,k]=yk+1−yk−(xi−k−xi−k−1)=yk+1−yk−ai−k\begin{aligned} &M[i,k+1]-M[i,k]\\ &\quad=y_{k+1}-y_k\\ &\qquad-(x_{i-k}-x_{i-k-1})\\ &\quad=y_{k+1}-y_k-a_{i-k} \end{aligned}

となる。行 ii を増やすと ai−ka_{i-k} は非増加なので、この利得は非減少である。yk+1−yky_{k+1}-y_k は ii に依存しないから、yy の差分がどんな並びでもよい。

つまり、合計個数を増やすほど、大きい右選択数が相対的に有利になる。この性質から、同点では小さい kk を選んだときの行最大位置は非減少になる。有効列範囲も行とともに右へ動くため、この範囲の変化も含めて正当性節で確かめる。これが最大値版のMonge性を使った探索であり、左選択数 j=i−kj=i-k の単調性を使うわけではない。

中央行を調べて上下へ再帰する

結合の探索には、対象行の区間 [s,t][s,t] と、それらの行の最適列が属する候補区間 [p,q][p,q] を渡す。最初は行 [2,L+R][2,L+R]、候補列 [1,R][1,R] である。

  1. s>ts>t なら終了する。そうでなければ中央行 h=⌊(s+t)/2⌋h=\lfloor(s+t)/2\rfloor を選ぶ。

  2. 候補区間と行の有効範囲の共通部分、すなわち次の範囲を小さい kk から走査する。

    max⁡(p,1,h−L)≤kk≤min⁡(q,R,h−1)\begin{gathered} \max(p,1,h-L)\leq k\\ k\leq\min(q,R,h-1) \end{gathered}

    最大値 zhz_h と、それを取る最小の列 k∗k_* を記録する。値が厳密に大きいときだけ更新すれば、この同点規約になる。

  3. 上半分の行 [s,h−1][s,h-1] には列 [p,k∗][p,k_*]、下半分の行 [h+1,t][h+1,t] には列 [k∗,q][k_*,q] を渡して再帰する。

行最大位置の単調性により、引き継いだ候補区間には各行の最適列が残る。初回から空行を除いているため、探索する中央行の共通部分は空にならない。各行で得た ziz_i を左右だけの答えと比較し、根の solve(0,N) が返す f1,…,fNf_1,\ldots,f_N を出力する。

典型の発動条件

分割統治による最大要素の所在分離

目的関数に選択集合の最大値があるとき、その値で並べて区間を分割することを考える。両側から選ぶなら最大値の担当を右へ固定できる。担当しない左側が単純な自由選択になるか、担当する右側が同じ部分問題になるかを確認する。

concave max-plus convolution

個数の分け方について max⁡k(xi−k+yk)\max_k(x_{i-k}+y_k) をまとめて求めたいとき、少なくとも片方の列の差分が非増加なら、最大値を取る位置の単調性を導ける。これを凹な列とのmax-plus畳み込みという。列の向き、同点の選び方、有効範囲を定義してから、中央行を走査する分割統治最適化へ進む。単に答えの列が単調というだけでは使えない。

問題固有の要素

左側には AA の和だけを持たせ、最大の BB を引く処理を右側の答えへ含めることで、二つの側の役割を変えている。左区間の答え uju_j をそのまま足すと、最大値を左でも余分に引いてしまう。

和の部分だけなら「大きいものから選ぶ」ことで凹な累積和になる。この性質を取り出せることが、単に最大値の所在を分けるだけでは終わらず、結合を高速化できる理由である。公式解説の分割と凹な列の畳み込みを基に、ここでは両側非空の有効域、小例、同点を含む探索手順を補っている。

正当性

一要素の区間では、非空の選択はその要素だけなので、基底 (−∞,Al−Bl)(-\infty,A_l-B_l) は正しい。左右の部分問題の答えが正しいと仮定して結合を考える。

任意の非空集合は、左だけ、右だけ、両側からのいずれか一つに属する。片側だけなら再帰の答えがそのまま最適値になる。両側から選ぶ場合、最大の BB は右で選んだ要素の最大値に等しい。左から jj 個、右から kk 個と固定すると、左右の選択は独立で、左の和の最大値 xjx_j と右の目的関数の最大値 yky_k は同時に達成できる。従って、有効域 max⁡(1,i−L)≤k≤min⁡(R,i−1)\max(1,i-L)\leq k\leq\min(R,i-1) での最大値が、両側から合計 ii 個選ぶ最適値に一致する。

次に、各行の左端の最大位置が非減少であることを示す。隣接列の差は考察で示したとおり行とともに非減少であり、その差を足せば、離れた二列 c<dc<d でも M[i,d]−M[i,c]M[i,d]-M[i,c] は両列が有効な行の範囲で非減少になる。また有効列区間の左端と右端も、それぞれ行とともに非減少である。

上の行の左端最大位置を dd、下の行の左端最大位置を cc とし、c<dc<d と仮定する。区間の両端の単調性により、この二列は両方の行で有効である。上の行では、より小さい列 cc が同点でも選ばれなかったので、列 dd の値が厳密に大きい。差の非減少性から下の行でも列 dd が厳密に勝ち、列 cc が最大位置であることに矛盾する。よって最大位置は非減少であり、中央行の最適列で上下の候補を制限しても各行の正解を失わない。

以上より結合は三種類の選択の最適値を漏れなく求め、その最大値を返す。区間長についての帰納法により、根で全個数の答えが得られる。BB が同値でも左の値が右の値以下である関係は保たれ、A,BA,B の符号にも依存しない。

実装上の注意

  • 区間の答えの0個目は常に −∞-\infty。一方、x0=0x_0=0 は和の累積用の初期値であり、この解説の結合では使わない。i=1i=1 の両側選択は存在しないので、左右だけの答えを比較する。
  • 中央行の走査は、再帰から来た候補区間と両側非空の有効域の共通部分に限る。同点で大きい列へ更新しない。どの行でも同じ規約を使うことが単調性の証明と対応する。
  • 入力は組のまま BB 順に並べる。左の AA を降順にするときは作業用配列を使い、元の BB 順を壊さない。同じ BB 同士の順は任意でよい。
  • 和や答えには符号付き64 bit整数を使う。有限な答えの絶対値は 4×10144\times10^{14} 以下なので、例えば番兵に −260-2^{60} を使える。無効な添字や番兵を加算する候補は評価せず、有限値だけを足して最大を取る。

復習の核

  • 集合の最大値を一度だけ引きたいときは、その値で並べ、分割後にどちら側が最大値を担当するかを固定する。
  • 凹性を持つのは「大きい順に選ぶ和」の列。もう片方の最適値の凹性を仮定せず、列間の差を行の方向に比較する。
  • 行を合計個数、列を右選択数と決めたら、有効域・同点規約・探索範囲の受け渡しまで同じ定義で通す。

計算量と制約

時間

O(Nlog⁡2N)O(N\log^2 N)。長さ n=L+Rn=L+R の区間では、左の AA の整列と累積和が O(nlog⁡n)O(n\log n)、中央行の走査による結合も O(nlog⁡n)O(n\log n) である。結合の各深さでは候補列区間が端点以外は重ならず、共有端点の分も含めて O(n)O(n) 回の評価に収まる。行の再帰の深さは O(log⁡n)O(\log n) で、行列の一要素は O(1)O(1) で評価できる。

外側の区間分割は O(log⁡N)O(\log N) 段あり、各段の区間長の和は NN なので、全体は O(Nlog⁡2N)O(N\log^2 N) となる。最初の BB 順の整列 O(Nlog⁡N)O(N\log N) と出力 O(N)O(N) もこの評価に含まれる。

空間

入力と作業領域を含めて O(N)O(N)。深さ優先で左右を解き、結合後に不要な子の答えや作業用配列を解放することを前提とする。先に解いた左の答えを保持して右へ進んでも、保持する区間長は幾何級数になり、合計 O(N)O(N) に収まる。外側と結合内の再帰スタックはそれぞれ O(log⁡N)O(\log N) であり、行列そのものは保存しない。全区間の答えや整列済み配列を解放せず残す実装では O(Nlog⁡N)O(N\log N) になる。

制約との対応

公式制約は 1≤N≤2×1051\leq N\leq2\times10^5、−109≤At≤109-10^9\leq A_t\leq10^9、−2×1014≤Bt≤2×1014-2\times10^{14}\leq B_t\leq2\times10^{14}。N=1N=1 は一要素の基底から直接出力できる。AA や BB が負でも、個数を固定した和の最適化と BB の昇順による大小関係は変わらない。制限時間は2秒、メモリ制限は1024 MiBであり、全個数と全分割を二重に列挙せず、上記の分割統治で処理する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Max (Sum - Max) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Monge・monotone minima最適化

主題
  • Monge・monotone minima最適化: quadrangle inequality/Monge性から各行の最適遷移位置が単調になることを示し、divide-and-conquerやSMAWKで最小値を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 再帰分割・分割統治: pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。

    主タグ: Monge・monotone minima最適化

    補助タグ: 再帰分割・分割統治

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

    学習の位置

    体系上の位置: Monge・monotone minima最適化

    • quadrangle inequality/Monge性から各行の最適遷移位置が単調になることを示し、divide-and-conquerやSMAWKで最小値を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • DP遷移を因数分解・集約して加速する — 正しい状態と遷移を作った後、共通項の因数分解や集約で同じDPを高速化する。
    • 再帰分割・分割統治 — pivot・bit・時刻区間・積木で部分問題へ再帰分割し、部分結果を重複なく合成する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題