TopCoder SRM 576 Div1 Medium TheExperiment

さてDiv1 Medium。
http://community.topcoder.com/stat?c=problem_statement&pm=12509

問題

間隔1毎にパイプが並び、それぞれ一定量の水が出る。
この下に、長さLのスポンジをM個置く。
各スポンジの給水量がA～Bとなるような置き方の組み合わせ数を答える。

なお、各スポンジが吸収するパイプが同じ組み合わせ同士は（例え位置がずれていても）同じ置き方とみなす。

解法

最後の１文、つまり位置はさほど重要でないことが重要。

途中長さL分の連続パイプを吸収するスポンジを置く場合、そこにつながる左右のスポンジはLより短いパイプの置き方ができる（はみ出る分は、長さLのスポンジの下側におけばよい）。

この事実を使うと、左から順にDPでスポンジ数をカウントしていけばよい。
その際、長さL以下で水量の合計A～Bとなるスポンジの置き方を加算していけばよい。
状態として途中で長さLのスポンジが１回でもあるかチェックしていく。

解説によると、位置のずれも列挙するとO(N^5)かかるが、位置のずれは無視して給水するパイプだけ気にすればO(N^3)で済む。
最初自分も問題文の最後の条件を見落としてO(N^5)のコードを書いてしまった…。

ll DP[301][301][2]; // Mth sponge, pos, 0-include L
ll fin[301][301]; // Mth sponge, pos

class TheExperiment {
	
	public:
	int countPlacements(vector <string> intensity, int M, int L, int A, int B) {
		int i,x,done,nx,l,y,j,x2;
		ll mo=1000000009;
		string S;
		int SL;
		int tot[302];
		
		FOR(i,intensity.size()) S+=intensity[i];
		SL=S.size();
		
		ZERO(tot);
		FOR(i,SL) tot[i+1]=tot[i]+(S[i]-'0');
		
		ZERO(DP);
		ZERO(fin);
		fin[0][0]=1;
		
		for(x=1;x<=SL;x++) {
			FOR(i,M+1) fin[i][x]=(fin[i][x-1]+DP[i][x-1][1])%mo;
			
			for(l=1;l<=L;l++) {
				if(x-l<0) break;
				if(tot[x]-tot[x-l]<A) continue;
				if(tot[x]-tot[x-l]>B) break;
				FOR(i,M) DP[i+1][x][1]=(DP[i+1][x][1]+DP[i][x-l][1]) % mo;
				FOR(i,M) DP[i+1][x][l==L]=(DP[i+1][x][l==L]+DP[i][x-l][0]+fin[i][x-l]) % mo;
			}
		}
		
		return (fin[M][SL]+DP[M][SL][1])%mo;
	}
};

まとめ

意外とコード量も少ない。
こういう問題をさらっと作れるセンスはうらやましい。