TopCoder SRM 768 : Div2 Hard MeanMedianCount

Div1 Easyの方が難しくない？
https://community.topcoder.com/stat?c=problem_statement&pm=15604

問題

N要素(奇数)の数列があり、各要素0～10の値を取れる。初期値は0である。

この数列の取りうる値は11^N通り考えられる。
そのうち、平均値Mean・中間値Medianを達成しているものは何通りか。

解法

単純なDP。
まずは下記を埋めよう。
F(i,a,b) := 先頭i要素まで値を決めたとき、Mean以上の値を持つ要素の個数がa、合計値がbとなる組み合わせ

あとはa≧(N+1)/2、b≧Median*Nの範囲でF(N,a,b)の総和を取るだけ。

ll from[26][500];
ll to[26][500];
ll mo=1000000007;

class MeanMedianCount {
	public:
	int getCount(int N, int needMean, int needMedian) {
		ZERO(from);
		from[0][0]=1;
		int i,x,y,z;
		FOR(i,N) {
			ZERO(to);
			FOR(x,min(25,i)+1) FOR(y,i*10+1) FOR(z,11) {
				(to[min(N/2+1,x+(z>=needMedian))][y+z]+=from[x][y])%=mo;
			}
			swap(from,to);
		}
		
		ll ret=0;
		for(x=needMean*N;x<=490;x++) ret+=from[N/2+1][x];
		return ret%mo;
		
	}
}

まとめ

最近Div2Hardがだいぶ簡単な気がする。