TopCoder SRM 582 Div1 Medium ColorfulBuilding

問題

n本のビルがあって、i番目のビルは色がC[i], 高さがiである。
このビルを一列に並べたとき、前から見て色の境界がL-1個であるような並べ方の総数を求めよ。

制約条件

n≦2500
L≦2500

方針

editorialがリンクはないんだけど存在する。謎。
http://apps.topcoder.com/wiki/display/tc/SRM+582

O(N^3)の方針がまずこんな感じ。

ビルを大きい順に並べる。
dp[使ったビルの数][見えるビルの数][最前列のビルの色] := 場合の数
として、次に使うビルを先頭にもってくるか、先頭以外に入れるかで遷移。

コードにするとこんな感じ。

	dp[0][1][C[0]] = 1;
	
	rep(i, n - 1) rep(j, L + 1) rep(k, C.size()){
		
		dp[i + 1][j][k] += (i + 1) * dp[i][j][k];
		
		if(k == C[i]){
			dp[i + 1][j][C[i]] += dp[i][j][k];
		}
		else{
			dp[i + 1][j + 1][C[i]] += dp[i][j][k];
		}
	}

で、この更新は
dp[i + 1][j][k]の書き換えと
dp[i + 1][j][ C[i] ]の書き換えの二つに分かれているのだけど、
前者はi+1倍するだけなので、わざわざrep(k, C.size())のループを毎回まわす必要がなさそう。
後者はsum[i] = Σ{dp[i][j] | j}を持っておけばループをまわさなくて済みそう。

で、DPを書き換えると以下のようになる。（ループを逆順にして配列は使いまわしている）

			for(int j = L; j > 0 ; j--){
				
				(sum[j] *= i) %= mod; //先頭以外に置く
				//先頭同じ色のやつなら先頭においてもj増えない、先頭違う色のやつの先頭に置いてj増やす
				(sum[j] += dp[j][C[i]] + sum[j - 1] - dp[j - 1][C[i]] + mod) %= mod;
				
				//先頭が同じやつだったらi+1通り
				(dp[j][C[i]] *= i + 1) %= mod;
				//先頭が違うやつから作る
				(dp[j][C[i]] += sum[j - 1] - dp[j - 1][C[i]] + mod) %= mod;
			}

で、これだと前のdpにおけるdp[i][j][違う色]を(i+1)倍していく処理が抜けている。
違う色を毎回ループで回したくなかったので、どうすればいいかというと、
違う色である間する掛け算を、色ごとにまとめておいて、
同じ色が出てきたらまとめておいた掛け算を掛ければよい。

ソースコード

const int mod = (int)1e9 + 9;

ll dp[2600][2600];
ll sum[2600];
ll pending[2600];

class ColorfulBuilding {
	public:
	int count(vector <string> color1, vector <string> color2, int L) {
		
		memset(dp, 0, sizeof(dp));
		memset(sum, 0, sizeof(sum));
		rep(i, 2600) pending[i] = 1;
		
		string a, b;
		rep(i, color1.size()){
			a += color1[i];
			b += color2[i];
		}
		int n = a.size();
		vi v, C;
		
		rep(i, n) v.pb((int)a[i] * 256 + b[i]);
		sort(all(v));
		v.erase(unique(all(v)), v.end());
		
		rep(i, n) C.pb(lower_bound(all(v), (int)a[i] * 256 + b[i]) - v.begin());
		reverse(all(C));
		
		
		dp[1][C[0]] = 1;
		sum[1] = 1;
		
		for(int i = 1; i < n; i++){
			
			rep(j, L + 1) (dp[j][C[i]] *= pending[C[i]]) %= mod;
			rep(j, C.size()) (pending[j] *= i) %= mod;
			pending[C[i]] = 1;
			
			for(int j = L; j > 0 ; j--){
				
				(sum[j] *= i) %= mod; //先頭以外に置く
				//同じ色のやつなら先頭においてもj増えない、違う色のやつの先頭に置いてj増やす
				(sum[j] += dp[j][C[i]] + sum[j - 1] - dp[j - 1][C[i]] + mod) %= mod;
				
				//先頭が同じやつだったらi+1通り
				(dp[j][C[i]] *= i + 1) %= mod;
				//先頭が違うやつから作る
				(dp[j][C[i]] += sum[j - 1] - dp[j - 1][C[i]] + mod) %= mod;
			}
		}
		
		return sum[L];
	}
};