TopCoder SRM 593 Div1 Medium MayTheBestPetWin

450ptのMediumだけど解けなかった…。
なお、このMediumはDiv2 Hardと同じ。
http://community.topcoder.com/stat?c=problem_statement&pm=12779

問題

N匹のペットは、それぞれ最短A[i]、最長B[i]の時間でトラックを1周走る。
ここで、N匹のペットをSとTの2つのチームに分けたい。
それぞれのチームのペットが1匹あたり1周ずつ順に走る場合、両チームのゴール時間の差の最大値を最小化せよ。

解法

ペットの集合Xに対するA[i]の和をA(X)、B[i]の和をB(X)とすると、ゴール時間の最大値は片方のチームの最長時間からもう片方の最短時間を引いたものなので、答えはmin(B(T)-A(S), B(S)-A(T))となる。

B(T)-A(S)やB(S)-A(T)をそのまま0に近づけようとすると、これらA(S),A(T),B(S),B(T)のうち2つの要素を使ってDPしないといけないが、これらは最大500000になるため、2要素で500000^2になるDPをしないといけないので間に合わない。

ここで、A(S)=A(S+T)-A(T)、B(S)=B(S+T)-B(T)と置くことができる。
すると求めるのはmin(B(T)+A(T)-A(S+T), B(S+T)-(B(T)+A(T)))とおける。
S+Tは常にN匹全体なので、A(S+T)およびB(S+T)は一定。
よって、あとA(T)+B(T)のとりうる範囲を求め、min(B(T)+A(T)-A(S+T), B(S+T)-(B(T)+A(T)))を求めればよい。
A(T)+B(T)の最大値はN*10000*20<=10^7であり、N回分DPして到達可能な値を列挙するだけなので間に合う。

int dp[1000001];
 
class MayTheBestPetWin {
	public:
	int N,TA,TB;
	int calc(vector <int> A, vector <int> B) {
		int i,x,y;
		N=A.size();
		TA=TB=0;
		FOR(i,N) TA+=A[i];
		FOR(i,N) TB+=B[i];
		
		ZERO(dp);
		dp[0]=1;
		
		FOR(i,N) {
			for(x=1000000-(A[i]+B[i]);x>=0;x--) {
				if(dp[x]) dp[x+A[i]+B[i]] = 1;
			}
		}
		
		int mi=10000000;
		FOR(i,1000001) if(dp[i]) {
			x = i-TA;
			y = TB-i;
			mi=min(mi,max(x,y));
		}
		return mi;
	}
}

まとめ

本番、元の式を変形してDPしやすくするまでは思いついたけど、上記の変形にはたどり着けなかった…残念。