AtCoder ABC #355 (東京海上日動プログラミングコンテスト2024) : G - Baseball

このテクなかなか覚えられない。
https://atcoder.jp/contests/abc355/tasks/abc355_g

問題

N要素の整数列Pが与えられる。
先手は1～Nのうちk個の値を選ぶ。
その後、1～Nのうち1つの値yがPに比例した確率で選ばれる。

先手の選んだK個の値と、yの差の絶対値の最小値が、先手の得るスコアをなる。
先手がスコアの期待値が最小となるようK個の値を選ぶとき、その値を求めよ。

解法

f(s,t) := 先手がsを選んだ次にtを選んだ場合、yがs～tの範囲を選ばれることによるスコアの寄与
とする。
dp(n,k) := 先頭からn要素目にk個目を選択したとき、yがn以下の範囲を選んだ場合のスコアの最小値
を求めて行けばよい。
ただし、愚直にdpを行うとdp(*,k)からdp(n,k+1)を求めることとなり、monotone minimaを使ってもO(NKlogN)かかってしまう。

そこで、これとAlienDPを併用する。
要素を1個選ぶときのコストCを三分探索し、K個選ぶときのコストが最小となるCを求めよう。
その過程でmonotone minimaを使っていく。

int N,K;
int P[50505];
ll PS[50505];
ll PL[50505];
ll PR[50505];
ll dp[50505];

ll lambda;

ll costL(int L,int R) {
	return (PL[R]-PL[L])-(PS[R]-PS[L])*(L);
}
ll costR(int L,int R) {
	return (PR[R]-PR[max(0,L-1)])-(PS[R]-PS[max(0,L-1)])*(N-R+1);
}

ll cost(int L,int R) {
	assert(L<R);
	if(L==0&&R==N+1) return 1LL<<60;
	if(L==0) return costR(L,R)+lambda;
	if(R==N+1) return costL(L,R)+lambda;
	int M=(L+R)/2;
	return costL(L,M)+costR(M+1,R)+lambda;
	
}

void dfs2(int le,int ri,int p1,int p2) {
	if(le+1>=ri) return;
	int mi=(le+ri)/2;
	int p3=p1;
	ll v=1LL<<60;
	for(int i=p1;i<=min(mi-1,p2);i++) if(chmin(v,dp[i]+cost(i,mi))) p3=i;
	dp[mi]=min(dp[mi],v);
	dfs2(le,mi,p1,p3);
	dfs2(mi,ri,p3,p2);
}

void dfs(int le,int ri) {
	if(le+1>=ri) return;
	int mi=(le+ri)/2;
	dfs(le,mi);
	ll p1=le,v1=1LL<<60;
	ll p2=le,v2=1LL<<60;
	for(int i=le;i<mi;i++) {
		if(chmin(v1,dp[i]+cost(i,mi))) p1=i;
		if(chmin(v2,dp[i]+cost(i,ri-1))) p2=i;
	}
	dp[mi]=min(dp[mi],v1);
	dp[ri-1]=min(dp[ri-1],v2);
	dfs2(mi,ri-1,p1,p2);
	
	dfs(mi,ri);
}

ll hoge(ll v) {
	lambda=v;
	int i;
	FOR(i,N+2) dp[i]=1LL<<60;
	dp[0]=0;
	dfs(0,N+2);
	return dp[N+1]-v*(K+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N+1) {
		if(i!=N) cin>>P[i];
		PS[i+1]=PS[i]+P[i];
		PL[i+1]=PL[i]+1LL*(i+1)*P[i];
		PR[i+1]=PR[i]+1LL*(N-i)*P[i];
	}
	
	ll CL=0,CR=1LL<<35;
	ll mi=max(hoge(CL),hoge(CR));
	while(CR-CL>=3) {
		ll M1=(CL*2+CR)/3;
		ll M2=(CL+CR*2)/3;
		ll V1=hoge(M1);
		ll V2=hoge(M2);
		if(V1>V2) CR=M2;
		else if(V2>V1) CL=M1;
		else CL=M1,CR=M2;
		mi=max({mi,V1,V2});
	}
	for(ll a=CL;a<=CR;a++) mi=max(mi,hoge(a));
	
	cout<<mi<<endl;
}

まとめ

本番monotone minima解までで止まってしまい、AlienDPに持ち込めなかった…。
利用する辺の数が決まってるような最短経路はAlienDP、覚えておこう…。