TopCoder SRM 575 Div1 Medium TheSwapsDivOne

久々に本番に解けたDiv1 Medium。
http://community.topcoder.com/stat?c=problem_statement&pm=12498

問題

0～9で構成された要素数L(<=2209)の配列が与えられる。
ここで、ランダムに配列中の２要素の位置を入れ替える作業をK(<=10^6)回行う。

最後に、この配列中で連続する要素からなる部分配列を選び、その合計を求める。
このとき、この合計値の期待値を求める。

解法

行う作業は以下の２つ。

• 配列中の各位置の数が最終的な合計値に与える期待値の算出
• ある位置にある数が、K回の入れ替え後に同じ位置にいる確率を算出

前者は、部分配列の選び方(L*(L+1)/2)通りに対し、部分配列の先頭と末尾が各位置を囲う組み合わせ数を求めればよい。O(L)で終わる。
後者は、X回後に元の位置にいる確率は、X-1回後に元の位置にいて、X回目に自分が選ばれない確率と、X-1回後に別の位置にいて、X回後に元の位置に戻る確率の和になる。
この計算を漸化式から計算すればよいのでO(K)。
なお、元の場所以外の場所にいる確率は、すべて同じ確率(1-P(X))/(L-1)でいると考えられる。

あとは各要素に対し、元の場所にいる場合の期待値と別の場所にいる場合の期待値を足せばよい。
合わせてO(L+K)なので時間は問題なし。

double P[1000002];
class TheSwapsDivOne {
	int L;
	double nc[2500];
	public:
	double find(vector <string> sequence, int k) {
		string s;
		int i,x,y;
		FOR(i,sequence.size()) s+=sequence[i];
		
		double tc=0;
		L=s.size();
		FOR(x,L) {
			nc[x]=(x+1)*(L-x)/(double)(L*(L+1)/2);
			tc+=nc[x];
		}
		
		P[0]=1;
		for(x=1;x<=k;x++) P[x]=P[x-1]*(L-2)/(double)L + (1-P[x-1])*(2/(double)L/(double)(L-1));
		
		double tt=0;
		FOR(x,L) tt += P[k]*nc[x]*(s[x]-'0') + (1-P[k])*(tc-nc[x])*(s[x]-'0')/(L-1);
		return tt;
	}

};

まとめ

Pは２項間漸化式なので、配列作る必要なかったな。
本番Easyで時間食ったおかげで提出は終了直前だったが、Medium自体はそこそこの時間で終わって良かった。