Codeforces #333 Div1 C. Kleofáš and the n-thlon

シンプルな問題設定で良い。
http://codeforces.com/contest/601/problem/C

問題

M人でN個の競技を行う。
各競技では、各人1～M位の順位がつく。
最終的な順位は、各競技の順位の和の小さい順に振られる。
正確には、自分より順位の和が小さい人がk人いる場合、(k+1)位である。

自分の各競技の順位X[i]が与えられる。
他の人の順位はわからないが、どうも各人残り(M-1)通りの順位を等確率で取るようだ。
自分の順位の期待値を求めよ。

解法

自分の順位の和をS=sum(X)とする。
DP[x][y] := (x個の競技を終えて順位の和がyである人の人数) とする。
最終的には、自分より少ない順位和の人数の期待値を求めればいいので、1+sum(DP[N][0..(S-1)])が解となる。

x番目の競技では、自分以外の人は1...M番のうちX[x]以外の順位を確率1/(M-1)で得るので、
DP[x][y] += sum(DP[x-1][y-i]/(M-1)) (i=1..MただしX[x]以外)
となる。ただこのDPをこのまま行うと、yの上限がN*Mまで行くのでO(N^2*M^2)に到達してTLEする。

上記式を少し書き換える。
DP[x][y] = (DP[x-1][y-1]+DP[x-1][y-2]+...+DP[x-1][y-(X[x]-1)]+DP[x-1][y-(X[x]+1)]..+DP[x-1][y-M])/(M-1)
ここでSDP[x][y]=sum(DP[x][0..y])とすると
DP[x][y] = (SDP[x-1][y-1]-SDP[x-1][y-M-1]-DP[x-1][y-X[x]])/(M-1)
と置くことができる。
SDPはDPの一番深いループではない部分で先に計算できるので、計算量を落とせる。

int N,M;
int X[1010];
int tot;
double from[1010100],to[1010100],sfrom[2010100];
const int SL=100002;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	if(M==1) return _P("1\n");
	
	double rev=1/(M-1.0);
	
	from[SL]=M-1;
	FOR(i,N) {
		cin>>X[i], tot+=X[i];
		FOR(x,100011) {
			sfrom[SL+x]=sfrom[SL+x-1]+from[SL+x];
			to[SL+x] = sfrom[SL+x-1] - sfrom[SL+(x-M-1)] - from[SL+x-X[i]];
			to[SL+x] *= rev;
		}
		swap(from,to);
	}
	
	double ret=1;
	FOR(i,tot) ret+=from[SL+i];
	_P("%.12lf\n",ret);
	
}

まとめ

これも本番頭をだいぶ抱えたけど、最終的に解けて良かった。