yukicoder : No.398 ハーフパイプ(2)

最初ちょっと考え込んでしまった。
http://yukicoder.me/problems/no/398

問題

ハーフパイプの採点では、審査員６名が100点満点で採点を行い、最高点の１名と最低点の１名を除いた４名の採点の平均値を演技の得点とする。
演技の得点Xが与えられるとき、得点がXとなるような６名の採点の組み合わせを求めよ。

解法

以下のような状態を考え、６人分DPで組み合わせ数を計算していこう。
dp[最低点][最高点][合計点] := 左記のような採点の組み合わせ数

(合計点)-(最低点)-(最高点) = 4*Xとなるような最低点・最高点・合計点に対しdp[最低点][最高点][合計点]の和を取ったものが解。

int A;

ll from[101][101][601];
ll to[101][101][601];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	double X;
	cin>>X;
	A=X*4+0.01;
	
	from[100][0][0]=1;
	FOR(i,6) {
		ZERO(to);
		FOR(x,101) FOR(y,101) FOR(j,i*100+1) if(from[x][y][j]) {
			FOR(k,101) to[min(x,k)][max(y,k)][j+k] += from[x][y][j];
		}
		swap(from,to);
	}
	
	ll ret=0;
	FOR(x,101) FOR(y,101) FOR(i,601) if(i-x-y==A) ret += from[x][y][i];
	cout<<ret<<endl;
}

まとめ

TLEになるかと思ったけど、意外に余裕あったね。