AtCoder ABC #348 (トヨタ自動車プログラミングコンテスト2024#4) : G - Max (Sum - Max)

このテクそんな名前あったのね。
https://atcoder.jp/contests/abc348/tasks/abc348_g

問題

N個の整数対(A[i],B[i])が与えられる。
これらの整数対からk個選ぶとき、選んだk個のA[i]の総和から、選んだk個のB[i]の最大値を引いた値を最大化したい。
k=1～Nの時、それぞれの値を求めよ。

解法

整数対をあらかじめB[i]の昇順に並べておく。
すると、この添字0～(N-1)からk個選び、添字iに対応するA[i]の総和から、選んだ添字の最大値jに対しB[j]を引いた値を求める問題となる。
分割統治の要領で、以下を求めよう。
f(L,R,k) := 添字L～(R-1)の範囲でk個選んだ時、その添字iに対応するA[i]の総和の最大値
g(L,R,k) := 添字L～(R-1)の範囲でk個選んだ時、その添字iに対応するA[i]の総和の最大値から、選んだ添字の最大値jに対しB[j]を引いた時の最大値

M=(L+R)/2とした時、

• f(a,b,k)はkに対し上に凸。そのため、f(L,M,*)とf(M,R,*)から、f(L,R,*)を求めるのはマージソートの要領で容易に行える。
• g(a,b,k)はkに対し上に凸とは限らない。f(L,M,*)とg(M,R,*)から、g(L,R,*)を求めるには、f(L,M,*)がkに対し上に凸なことを活かし、Monotone Minimaの要領で求めて行く。

int N;
pair<ll,ll> P[202020];


vector<ll> max_plus_conv(vector<ll>& A,vector<ll>& B) {
	// C[i]=max(A[x]+B[i-x]) Bは上に凸、AB逆だとダメ
	int N=A.size(),M=B.size();
	vector<ll> C(N+M-1,-1LL<<60);
	
	auto get=[&](int a,int b) {
		if(a<0||a>=N+M||b<0||b>=N||a-b<0||a-b>=M) return -1LL<<60;
		return A[b]+B[a-b];
	};
	
	auto dfs=[&](auto self,int NL,int NR,int ML,int MR) {
		if(NL>=NR||ML>=MR) return;
		int NM=(NL+NR)/2;
		int TM=ML;
		ll TV=-1LL<<60;
		for(int x=ML;x<MR;x++) {
			ll v=get(NM,x);
			if(chmax(TV,v)) TM=x;
		}
		C[NM]=TV;
		self(self,NL,NM,ML,TM+1);
		self(self,NM+1,NR,TM,MR);
	};
	
	
	dfs(dfs,0,N+M-1,0,N);
	return C;
	
}

pair<vector<ll>,vector<ll>> dfs(int L,int R) {
	vector<ll> As(R-L+1,-1LL<<60),ABs(R-L+1,-1LL<<60);
	
	if(L+1==R) {
		As={0,P[L].second};
		ABs={-1LL<<60,P[L].second-P[L].first};
		return {As,ABs};
	}
	int M=(L+R)/2;
	auto a=dfs(L,M);
	auto b=dfs(M,R);
	int i;
	int x=0,y=0;
	As[0]=0;
	for(i=1;i<=R-L;i++) {
		if(x==a.first.size()-1) y++;
		else if(y==b.first.size()-1) x++;
		else if(a.first[x+1]-a.first[x]>b.first[y+1]-b.first[y]) x++;
		else y++;
		As[i]=a.first[x]+b.first[y];
	}
	
	ABs=max_plus_conv(b.second,a.first);
	FOR(i,a.second.size()) ABs[i]=max(ABs[i],a.second[i]);
	FOR(i,b.second.size()) ABs[i]=max(ABs[i],b.second[i]);
	
	return {As,ABs};
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].second>>P[i].first;
	sort(P,P+N);
	
	auto a=dfs(0,N);
	FOR(i,N) cout<<a.second[i+1]<<endl;
}

まとめ

このテクCodeforcesで昔見た記憶あるんだけど、その時名前を見た記憶がないんだよな。