E - Good Partition Editorial
by 
Mitsubachi
0-indexed で考えます。この問題は以下のように言い換えることができます。
これは辺コストを $-1$ 倍することで最短パスの問題へ帰着できます。以降はこれを考えます。ここで、 $c \left( i, j \right) = \min_{i \leq k < j} \left( a_k \right) - \max_{i \leq k < j} \left( a_k \right)$ を $i$ から $j$ への辺のコストとします。
動的計画法を考えます。 $\mathrm{dp}[j]$ を頂点 $j$ までの最短コストとして、遷移は $\mathrm{dp}[j] = \min_{i < j} \left( \mathrm{dp}[i] + c \left( i ,j \right) \right)$ です。
ここで、 \(i < j < k < l\) について \(c \left(i,l \right) + c \left( j,k \right) \geq c \left( i, k \right) + c \left( j,l \right)\) が成立します。
証明 $1$
この証明の間に限り、辺コストを $-1$ 倍する前に言い換えます。すなわち $c \left( i,j \right) = \max_{i \leq k < j} \left( a_k \right) - \min_{i \leq k < j} \left( a_k \right)$ です。
示したいものは $c \left(i,l \right) + c \left( j,k \right) \leq c \left( i, k \right) + c \left( j,l \right)$ になります。
移項すると $c \left(i,l \right) - c \left( i, k \right) \leq c \left( j,l \right) - c \left( j,k \right)$ を示せば良いです。
各辺の意味は $[\blacksquare,k)$ における最大値と最小値の差と $[\blacksquare,l)$ における最大値と最小値の差の $2$ つの値の差分と捉えることができます。
$\blacksquare$ の値が小さければ小さいほど、すなわち左端が左にあるほど、右端を伸ばしても値が変わりにくいことが直感的に理解できます。
よって証明できました。厳密に数式で書く場合は $[i,j),[j,k),[k,l)$ における最大値や最小値の大小関係で場合分けを行えば良いです。
証明 $2$
$c' \left( i, j \right) = \min_{i \leq k < j} \left( a_k \right)$ として、 $c'$ について上のような式が成り立っていることを示します。
$[i, l)$ における $a$ の最小値を取る要素が $[i, k)$ の中に存在するとき $c' \left( i, l \right) = c' \left( i, k \right)$ です。 $[j, k)$ は $[j, l)$ の部分区間なので $c' \left( j, k \right) \geq c' \left( j, l \right)$ となります。
そうでない場合、 $[i, l)$ における $a$ の最小値を取る要素は $[k, l)$ の中に存在します。よって $c' \left( i, l \right) = c' \left( j, l \right)$ です。 $[j, k)$ は $[i, k)$ の部分区間なので $c' \left( j, k \right) \geq c' \left( i, k \right)$ となります。
いずれの場合でも得られる $2$ つの式を足し合わせることで $c' \left( i, l \right) + c' \left( j, k \right) \geq c' \left( i, k \right) + c' \left( j, l \right)$ が言えます。
$c'' \left( i, j \right) = - \max_{i \leq k < j} \left( a_k \right)$ として、 $c''$ について上のような式が成り立っていることを示します。
これは $a$ の各要素を $-1$ 倍したときの $c'$ に相当すると考えると上の結果より導かれます。
$c \left( i, j \right) = c' \left( i, j \right) + c'' \left( i, j \right)$ であるので、全体が示されました。
このような $c$ は Monge 性を満たしています。
Monge 性を満たしているグラフは高速に計算できることが知られています。詳細は以下の資料に譲ります。
下の実装例の場合、 \(c\) を segtree を用いて \(O \left( \log N \right)\) で求めているので、全体の計算量は \(O \left( N \log^2 N \right)\) です。
実装例
#include <iostream>
using namespace std;
#include <atcoder/segtree>
using namespace atcoder;
using P = pair<long long,long long>;
P op(P a,P b){
return {max(a.first,b.first),min(a.second,b.second)};
}
P e(){
return {-1e18,1e18};
}
// https://noshi91.hatenablog.com/entry/2023/02/18/005856
// T は辺コストの型
// cost(i,j) は頂点 i -> 頂点 j へのコスト(型 T)を返す関数
// 頂点番号は 0-ind
// 返り値は配列 dist で dist[i] が 0 -> i の最小コストに相当
// a[i][j] を j -> i を最後にするコスト dist[j]+cost(j,i) とする(j < i)
// a[i] が最小値を取るような j が欲しい これを amin で管理
template <typename T,typename F>
vector<T> monge_shortest_path(int n,T inf,const F & cost){
vector<T> dist(n,inf);
dist[0]=0;
vector<int> amin(n,0);
auto check=[&](int i,int k){
// k -> i に行くもので暫定の最小値を更新できるかを確認
if(k>=i)return;
auto dist2=dist[k]+cost(k,i);
if(dist2<dist[i]){
dist[i]=dist2;
amin[i]=k;
}
};
auto subsolve=[&](auto& subsolve,int l,int r){
// (l,r] について dist を計算する
if(r-l==1)return;
int m=(l+r)/2;
for(int k=amin[l];k<=amin[r];k++)check(m,k);
subsolve(subsolve,l,m);
for(int k=l+1;k<=m;k++)check(r,k);
subsolve(subsolve,m,r);
};
check(n-1,0);
subsolve(subsolve,0,n-1);
return dist;
}
int main(){
int n;cin>>n;
vector<long long> a(n);
for(int i=0;i<n;i++)cin>>a[i];
segtree<P,op,e> seg(n);
for(int i=0;i<n;i++)seg.set(i,{a[i],a[i]});
auto cost=[&](int i,int j){
auto [mx,mn]=seg.prod(i,j);
return mn-mx;
};
auto dist=monge_shortest_path<long long>(n+1,1e18,cost);
cout<<-dist[n]<<endl;
}
posted:
last update: