TopCoder SRM 582 Div1 Medium ColorfulBuilding

600ptのMediumで非常に正解者の少なかった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12583

問題

N(<=1296)個の建物があり、高さは順に1～Nである。
また、それぞれの建物には色がついている。

これらの建物は1列に並んでおり、遠くから見たらL個の建物に見えた。
なお、ある建物の手前に同じ色の建物がある場合、それらは1つの建物に見える。
この時、L個の建物に見えるような建物の並び順の組み合わせ数を答えよ。

解法

Editorialにもあるが、O(N^3)ならすんなり思いつく。
建物を高い順に配置し、今まで何個分の建物が見えるかと、一番手前の建物の色の状態を持ってDPすればよい。

1. i番目の建物を一番手前以外に置く場合、すでに置いた(i-1)個の影に隠れるので、見える建物数や手前の色は変わらず、組み合わせ数は(i-1)倍になる。
2. i番目の建物を一番手前に置く場合：
   1. 一番手前と色が同じなら見える建物の数も手前の色も変わらないので、(i-1)番目までの組み合わせ数を加算
   2. 一番手前と色が違うなら、見える建物の数を1加算し、一番手前の建物の色を差し替えて(i-1)番目までの組み合わせ数を加算

ただ、O(N^3)ではN<=1296では間に合わない。

ここで計算量を落とせそうなのが色。
1や2-2の処理は各色ごとに同じ計算を行うだけなので、これをN回も行うのはもったいない。
よって、そこは全色の合計値を1つだけ持ち、たとえば1なら合計値だけを(i-1)倍すればよい。
この際、個々の色についても(i-1)倍したりしないといけないが、それは個々の色の値を実際に参照するときまで処理を遅延させる。
これらによりO(N^2)に落とせる。

int N,NC;
vector<int> C;
ll mo=1000000009;
ll dp[1300][1300],ped[1300],tot[1300];
map<int,int> S;

class ColorfulBuilding {
	public:
	string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
	int count(vector <string> color1, vector <string> color2, int L) {
		int i,j,x,y;
		string c1=concatvec(color1), c2=concatvec(color2);
		N=c1.size();
		
		C.clear();
		S.clear();
		for(i=N-1;i>=0;i--) {
			int u1=(c1[i]<='Z')?(c1[i]-'A'):(c1[i]-'a'+26);
			int u2=(c2[i]<='Z')?(c2[i]-'A'):(c2[i]-'a'+26);
			if(S.find(u1*52+u2)==S.end()) S[u1*52+u2] = S.size()-1;
			C.push_back(S[u1*52+u2]);
		}
		NC=S.size();
		
		ZERO(dp);
		ZERO(tot);
		dp[1][C[0]]=tot[1]=1;
		FOR(i,NC) ped[i]=1;
		
		for(i=1;i<N;i++) {
			int co=C[i];
			FOR(x,N+1) dp[x][co] = (dp[x][co] * ped[co]) % mo;
			FOR(x,NC) ped[x] = (ped[x]*i) % mo;
			ped[co]=1;
			
			for(x=N;x>=1;x--) {
				tot[x] = (tot[x]*i + dp[x][co] + tot[x-1] - dp[x-1][co]) % mo;
				if(tot[x]<0) tot[x]+=mo;
				dp[x][co] = (dp[x][co]*(i+1) + tot[x-1] - dp[x-1][co]) % mo;
				if(dp[x][co]<0) dp[x][co]+=mo;
			}
		}
		
		ll ret = 0;
		FOR(x,NC) ret += (dp[L][x]*ped[x])%mo;
		return (int)(ret%mo);
	}
};

まとめ

O(N^3)のコードをよく見ると、「合計値だけ計算すればうまくいけるんじゃ？」とは思ったけど、乗算処理を遅延させる、というのは自力では思いつかなかった。