8VC Venture Cup 2016 - Elimination Round : F. Group Projects

問題文を読み間違えてたことにさっき気づいた。
http://codeforces.com/contest/626/problem/F

問題

N人の学生がおり、各スキルはA[i]である。
これらの学生を幾つかのグループに分けたい。
グループのimbalanceとは、グループ内学生のスキルの最大値と最小値の差である。

全グループのimbalanceの合計がK以下になるようなグループの分け方は何通りあるか。

解法

学生をスキル順にソートする。
学生を幾つかのスキル値のrangeに収まるように分けることにする。

途中、閉じていない(rangeの最大値となる学生がグループにまだ割り当てられていない)グループが何個あるかを管理していこう。
i番の学生とi+1番の学生のスキルA[i]～A[i+1]を含むようなrangeがg個ある場合、imbalanceの総和にはg*(A[i+1]-A[i])個寄与する事を用いる。

以下のように状態を取る。
dp[s][g][t] := s番目の学生をグループに分けたとき、g個のrangeがまだ閉じていなくて、ここまでの合計imbalanceがtであるようなグループの分け方

dp[s][g][t]に対し、s+1番目の学生をどうグループに分けるかでdp[s+1][*][*]の値を更新する。
tはt≦Kの範囲だけ考えればよい。

• 単独でグループを作る : dp[s+1][g][t+(A[s+1]-A[s])*g] += dp[s][g][t]
• 既存のgグループのどこかに入る。グループの最大値とならず、グループを閉じさせない。 : dp[s+1][g][t+(A[s+1]-A[s])*g] += g*dp[s][g][t]
• 既存のgグループのどこかに入る。そのグループを閉じる。 : dp[s+1][g-1][t+(A[s+1]-A[s])*g] += g*dp[s][g][t]
• 新規に開いたグループを作る。：dp[s+1][g+1][t+(A[s+1]-A[s])*g] += dp[s][g][t]

あとがdp[N][0][*]の総和を求めると解になる。

int N,K;
int A[5050];
ll from[202][1010];
ll to[202][1010];
ll mo=1000000007;

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);
	
	from[0][0]=1;
	FOR(i,N) {
		int dif=i?A[i]-A[i-1]:0;
		ZERO(to);
		FOR(x,i+1) FOR(y,K+1) if(from[x][y] && y+dif*x<=K) {
			// same or add
			(to[x][y+dif*x] += (1+x)*from[x][y])%=mo;
			// open
			(to[x+1][y+dif*x] += from[x][y])%=mo;
			// close
			if(x) (to[x-1][y+dif*x] += x*from[x][y])%=mo;
		}
		swap(from,to);
	}
	
	ll ret=0;
	FOR(y,K+1) ret+=from[0][y];
	cout<<ret%mo<<endl;
}

まとめ

最近Codeforces系で自分のやらかしがひどすぎないですかね。