TopCoder SRM 593 Div1 Medium MayTheBestPetWin
問題
動物がn匹いて、2チームに振り分けてリレーをする。
それぞれの動物は、自分の区間をA[i]秒以上B[i]秒以下のどれかの時間で走る。
二つのチームの走行時間の差の最大値が最小になるようなチーム分けにおける、
走行時間の差の最大値を求めよ。
制約条件
n≦50
A[i], B[i]≦10000
方針
片方のチームをSとする。
走行時間差が最大になるのは、Sのチーム全員がA[i]で走って残りのチームが全員B[i]で走った場合か、
Sのチーム全員がB[i]で走って残りのチームが全員A[i]で走った場合。
前者の場合Sの走行時間はΣ[i∈S]Aiで、このときの差の最大値は、
ΣBi - Σ[i∈S](Ai + Bi)
後者の場合
ΣAi - Σ[i∈S](Ai + Bi)
なので、Ai + Biの取りうる値を調べれば、
そのときの前者、後者の走行時間差が求められ、
そのmaxを取れば一つのチームわけにおける時間差の最大値が求まることになる。
Ai + Biの取りうる値すべてはDPで簡単にもとまる。
ソースコード
bool dp[1100000]; struct MayTheBestPetWin{ int calc(vector <int> A, vector <int> B){ int n = A.size(); int ans = inf, a = 0, b = 0; dp[0] = 1; rep(i, n){ a += A[i]; b += B[i]; for(int j = 1100000 - 1; j >= 0; j--) if(dp[j] && j + A[i] + B[i] < 1100000) dp[j + A[i] + B[i]] = 1; } rep(i, 1100000) if(dp[i]){ ans = min(ans, max(abs(b - i), abs(a - i))); } return ans; } };