TopCoder SRM 453 Div1 Medium TheTournamentDivOne

問題

nチームが何試合か試合をした。
同じ組み合わせのチームが何回か対戦した、または一度も対戦していないチームの組み合わせがあることがある。

試合で勝ったチームにはw点が入り、試合が引き分けだと両方のチームにd点が入る。
全てのチームの得た得点が与えられるとき、
そのような得点を実現する試合回数の最小値を求めよ。

どのように試合と勝敗を組み合わせても、その得点が得られないときは、-1を返せ。

制約条件

n≦50
それぞれのチームの得点≦10000
w, d≦10000

方針

Editorial読んだけどあんまちゃんとわかってない。
以下わかった部分だけ。

それぞれのチームが引き分けた回数の和をsumd, それぞれのチームが引き分けた回数の最大値をmaxdとすると、
sumd ≧ 2 * maxdかつ、sumdが偶数のとき、
試合の組み合わせ方が存在し、かつ試合の組み合わせかたが存在するのはそのときに限る。

十分条件は帰納法で証明するっぽい。
maxd = 1のときは明らか。
maxd = k - 1のとき成り立つと仮定すると、maxd = k（k≧2）のとき、
引き分けの回数がk回のチームがmチームいたとする。

m≦2のとき、引き分け回数の多いチーム2チームが引き分けてない場合に還元する。
するとmaxdは1減って、sumdは2減るので、k - 1の場合から割り当てが存在することが言える。
m≧3のとき、
ceil(m/2) * 2チームが引き分けてない場合に還元する。
sumd≧mk≧2k + m - 1
（これはmk - 2 * k - m = (n - 2)(k - 1)≧-1から言える）
となって、
sumd - m - 1≧2k - 2≧2(k - 2)

なので、k - 1の場合から割り当てが存在することが言える。

条件がわかったので、存在する割り当てを適当に試していけばいい。

ソースコード

class TheTournamentDivOne {
	public:
	int find(vector <int> points, int w, int d) 
	{
		int n = points.size();
		int sum = 0;
		rep(i, n) sum += points[i];
		
		if(sum == 0) return 0;
		
		vi D(n);
		rep(i, n){
			D[i] = 10000;
			while(D[i] >= 0){
				if(points[i] >= d * D[i] && (points[i] - d * D[i]) % w == 0)
					break;
				D[i]--;
			}
			if(D[i] < 0) return -1;
		}
		int ans = -1;
		while(1){
			int dsum = 0;
			rep(i, n) dsum += D[i];
			int mxi = 0;
			rep(i, n) if(D[i] > D[mxi]) mxi = i;
			
			if(dsum % 2 == 0 && dsum >= 2 * D[mxi]){
				int tmp = dsum / 2 + (sum - d * dsum) / w;
				if(ans < 0 || tmp < ans) ans = tmp;
			}
			D[mxi]--;
			while(D[mxi] >= 0){
				if(points[mxi] >= d * D[mxi] && (points[mxi] - d * D[mxi]) % w == 0)
					break;
				D[mxi]--;
			}
			if(D[mxi] < 0) break;
		}
		return ans;
	}
};