kmjp's blog

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

Codeforces #317 Div1 B. Minimization

こちらは焦って手抜き回答でMLEしてしまった。
http://codeforces.com/contest/571/problem/B

問題

n要素の数列Aが与えられる。
Aの要素を任意に並べ替えられるとき、整数kに対して \displaystyle \sum_{i=1}^{n-k} | A[i] - A[i+k] |を最小化せよ。

解法

Aを昇順ソートした数列をBとする。
(Aを0-originで考えると)、数式の値は|A[0]-A[k]| + |A[k]-A[2*k]| + .... + |A[1]-A[1+k]| + |A[1+k]-A[1+2*k]| ...
となるので、A[0],A[k],A[2k]...を順にB[0],B[1],B[2]...と代入していけば良い。

このように、Bの連続した要素をA[i*k+j]=B[j*(n/k)+i]のように代入していくと良い。
ただ、n%kが0以外の時注意が必要である。
A[j],A[k+j],A[2k+j]...A[(n/k)*k+j]の数列は、要素数が(n/k)個ものが(k-(n%k))個、(n/k+1)個のものが(n%k)個ある。

つまりこの問題は以下のように言い換えられる。
Bを昇順ソートし、それらを要素数が(n/k)個ものが(k-(n%k))個、(n/k+1)個のものが(n%k)個の連続した要素群に分類する。
各要素群における最大値と最小値の差の総和を最小化せよ。

この問題ではkが5000以下のため、Bの先頭i要素をどう分類するかに対し、
dp[要素数(n/k)個の要素群の数][要素数(n/k+1)個の要素群の数] := i個目までの要素を(n/k)個または(n/k+1)個単位で分類したときの、各要素群における最大値と最小値の差の総和の最小化
としてDPしていけば良い。
最初のソートと合わせて、O(N*logN+K^2)で終わる。

int N,K;
ll A[303030];
ll dp[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	int step=N/K;
	int large=N%K,small=K-large;
	memset(dp,0x7f,sizeof(dp));
	dp[0][0]=0;
	FOR(x,large+1) FOR(y,small+1) {
		int pos=x*(step+1)+y*step;
		if(x<large) dp[x+1][y]=min(dp[x+1][y],dp[x][y]+A[pos+step]-A[pos]);
		if(y<small) dp[x][y+1]=min(dp[x][y+1],dp[x][y]+A[pos+step-1]-A[pos]);
	}
	cout<<dp[large][small]<<endl;
	
}

まとめ

この回はホント雑すぎた。