SRM 593 Div1 450 MayTheBestPetWin

2013-10-06

18:09 |

N匹の動物たちが2チームに分かれてリレー競走をする。動物 i は A[i]〜B[i] の時間で走る。
チーム分けが決まると、チームの合計タイムの差としてありうる値の最大値が決まる。その値が最小になるようにチーム分けしたとき、その最小値を求めよ。
2≦N≦50, 1≦A[i], B[i]≦10,000

わからん B[i]-A[i] すると何かに使えるか？
...

終了

@nico_shindanninさんの生放送を見る. ＼オススメですよ／（宣伝）
Sum[i] = A[i]+B[i] と置くと、答えはうまく Sum[i] だけで表せるようだ
|S fast - T slow| = |ΣA[s] - ΣB[t]| = |(SumA - ΣA[t]) - ΣB[t]| = |SumA - ΣSum[t]| (s in S, t in T)
|S slow - T fast| = |ΣB[s] - ΣA[t]| = |(SumB - ΣB[t]) - ΣA[t]| = |SumB - ΣSum[t]| (s in S, t in T)
おおおおお

↓あとで(accepted in practice room)

class MayTheBestPetWin {
	public:
	int calc(vector <int> A, vector <int> B) {
		int N = A.size();
		VI SUM(N);
		REP(i, N) SUM[i]=A[i]+B[i];
		int sumA = accumulate(ALL(A), 0);
		int sumB = accumulate(ALL(B), 0);
		int maxK = 10000 * N * 2 + 500;
		VVI dp(2, VI(maxK));
		int men=0;
		dp[men][0] = 1;
		REP(i, N) {
			REP(k, maxK) {
				if(dp[men][k]==0) continue;
				dp[1-men][k] = 1;
				dp[1-men][k + SUM[i]] = 1;
				assert(k + SUM[i] < maxK);
			}
			men ^= 1;
		}
		int ans = 1<<30;
		REP(k, maxK) {
			if(dp[men][k]) ans = min(ans, max(abs(sumA-k), abs(sumB-k)));
		}
		return ans;
	}
};