TopCoder SRM 542 Div2 Hard StrangeDictionary

これは割と簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11929

問題

N文字のdistinctな文字列からなる配列Wが与えられる。
この配列を以下のルールでソートする。

• 0～(N-1)のpermutationで構成される配列Pがランダムで均等の確率で生成される。
• 配列中の各文字をこの配列Pの数値をindexとして並べ替えた文字列を用いて、辞書順大小比較する。

元の文字列のソート後のindexの期待値を答えよ。

解法

ある文字列がある文字列の後に来るなら、indexが1増える。
各2つの文字列A,Bについて、Aが後に来る確率は、A[i]>B[i]となるようなiがP中で先に来ることであり、Bが後に来る確率はA[i]

• Aのindexの期待値は(A[i]>B[i]となるiの数)/(A[i]!=B[i]となるiの数)
• Bのindexの期待値は(A[i]

class StrangeDictionary {
	public:
	vector <double> getExpectedPositions(vector <string> words) {
		int N=words.size();
		int x,y,i;
		vector<double> id(N,0);
		
		FOR(x,N) FOR(y,N) if(x<y) {
			int x1=0,y1=0;
			FOR(i,words[0].size()) {
				if(words[x][i]<words[y][i]) y1++;
				if(words[x][i]>words[y][i]) x1++;
			}
			id[x] += x1/(double)(x1+y1);
			id[y] += y1/(double)(x1+y1);
		}
		return id;
	}
};

まとめ

permutationを考えると大変だけど、「先に2つの文字列の差ができるindex」を考えると簡単。