TopCoder SRM 520 Div1 Medium SRMIntermissionPhase

一つ勉強になった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11496

問題

3問のSRMの最大スコアpoint[3]が与えられる。
各問正解者は1～point[i]のいずれかのスコアが手に入る。

ここで、N人の3問の正答の有無が与えられる。
N人のスコアが降順となるような各門の取得スコアの組み合わせを求めよ。

解法

各問題のスコア最大値をMとする。

各人のスコアがS[i]であるには、1つ上位の人のスコアがS[i]+1以上であればよい。
この組み合わせ計算は累積和を用いれば1人当たりO(M)でできる。
このDPはDiv1 Easyクラスである。

問題は、各人のスコアがS[i]となるような3問の取得スコアの組み合わせ数である。

正解数が1問なら用意で、その問題iに対しpoint[i]>=S[i]なら1通り、point[i]

ll mo=1000000007;
ll dp[22][200010];
ll pat[8][200010];
ll pat2[200010];

class SRMIntermissionPhase {
	public:
	int N;
	int countWays(vector <int> points, vector <string> description) {
		int i,j;
		int mi,ma;
		
		ZERO(pat);
		ZERO(pat2);
		pat[0][0]=1;
		FOR(i,200001) {
			if(1<=i && i<=points[0]) pat[1][i]=1;
			if(1<=i && i<=points[1]) pat[2][i]=1;
			if(1<=i && i<=points[2]) pat[4][i]=1;
			mi=max(1,i-points[1]),ma=min(points[0],i-1);
			if(mi<=ma) pat[3][i]=ma-mi+1;
			pat2[i+1]=pat2[i]+pat[3][i];
			mi=max(1,i-points[2]),ma=min(points[0],i-1);
			if(mi<=ma) pat[5][i]=ma-mi+1;
			mi=max(1,i-points[2]),ma=min(points[1],i-1);
			if(mi<=ma) pat[6][i]=ma-mi+1;
		}
		FOR(i,200001) {
			mi=max(1,i-points[2]),ma=i-1;
			if(mi<=ma) {
				pat[7][i]=pat2[ma+1]-pat2[mi];
			}
		}
		
		
		N=description.size();
		ZERO(dp);
		dp[0][200001]=1;
		FOR(i,N) {
			int cur=(description[i][0]=='Y')+(description[i][1]=='Y')*2+(description[i][2]=='Y')*4;
			ll tot=0;
			for(j=200001;j>=0;j--) {
				dp[i+1][j]=tot*pat[cur][j]%mo;
				tot=(tot+dp[i][j])%mo;
			}
		}
		
		ll tot=0;
		for(j=200001;j>=0;j--) tot+=dp[N][j];
		return (int)(tot%mo);
	}
};

まとめ

とにかく累積和を使いまわす問題。
最後に書いた「X変数で各変数の範囲がMある場合、愚直に総当たりするとO(M^(X-1))かかるが累積和を何度も使うとO(M*X)で済ませる」のアイデアは色々使えそうだ。