kmjp's blog

競技プログラミング参加記です

Codeforces #190 Div1 E. Ciel and Gondolas

この考え方は面白かった。
http://codeforces.com/contest/321/problem/E

問題

N人の人が一列に並んでいるので、この列をK個のグループに分割したい。
分割後の各グループは1人以上いなければならない。

この時、i番とj番の人が同じグループにいたら、Q[i][j]のスコアがもらえる。
総スコアを最大化せよ。

解法

まずa番~b番の連続する人が同じグループにいる場合、その総スコアsum(a,b)をO(1)で出せるように累積和を取っておく。

シンプルな回答としては、[今見ている人の番号][残りグループ数]で状態を持ち、最大スコアを更新すればよい。
dp[id][groups] = max(dp[k][groups-1]+sum(k+1,id) )のような感じ。
ただしこれだとO(N^2*K)かかりTLEする。
この計算量を何とかしなければならない。

ここからEditorialを見て回答。
dp[id][groups] = max(dp[k][groups-1]+sum(k+1,id) )
について、最大値となるkをopt[id][groups]とする。
すなわちdp[id][groups] = dp[opt[id][groups]][groups-1]+sum(opt[id][groups]+1,id)。

このopt[id][groups]はidに対し昇順で、
opt[0][groups] ≦ opt[1][groups] ≦ opt[2][groups] ....
となる。

よってdp[id][groups-1]が一通り定まっているとき、二分探索を使いopt[id][groups]を求める。
元のO(N^2*K)の式では、0 ≦ opt[id][groups] < idとなるので時間がかかっていた。
しかしまずopt[N/2][groups]を求めておけば、id>N/2においてopt[N/2][groups] ≦ opt[id][groups] < idとなるので検索範囲が縮まる。
あとは同様に範囲を半々にしていく。

これにより全体でO(N*K*logN)程度の計算量に落とすことができる。

int N,K;
int U[5002][5002];
int S[5002][5002];
ll dp[5002][5002];

int costs(int l,int r) {
	return (S[r+1][r+1]-S[l][r+1]*2+S[l][l])/2;
}
void dodo(int step,int L,int R,int OL,int OR) {
	if(L>R) return;
	int M=(L+R)/2;
	int i,op;
	for(i=OL;i<=OR;i++) {
		if(dp[step][M+1]>dp[step-1][i]+costs(i,M)) {
			dp[step][M+1] = dp[step-1][i]+costs(i,M);
			op=i;
		}
	}
	dodo(step,L,M-1,OL,op);
	dodo(step,M+1,R,op,OR);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(y,N) FOR(x,N) cin>>U[y][x];
	FOR(y,N) {
		FOR(x,N) S[y+1][x+1]=S[y+1][x]+U[y][x];
		FOR(x,N) S[y+1][x+1]+=S[y][x+1];
	}
	FOR(y,N+1) FOR(x,N+1) dp[y][x]=1LL<<40;
	dp[0][0]=0;
	FOR(k,K) dodo(k+1,0,N,0,N);
	cout << dp[K][N] << endl;
}

まとめ

optが昇順になることは推測ついても、その後こういう二分探索を行うことは思いつかなかった。
このテクは覚えておこう。