SRM 542 Div2 Hard StrangeDictionary

問題

http://apps.topcoder.com/wiki/display/tc/SRM+542
長さが等しい文字列が複数与えられる。文字列中のランダムな2箇所を置換するのをランダムな回数行う処理をすべての文字列について行う。処理後の文字列をソートした時に当初の文字列が何番目に置かれるかの期待値を求めよ。

やりかた

Editorialを参考にしました。

あるふたつの文字列i, jについて考える。ランダムな置換をおこなった後にiが前に来る期待値は、2つの文字列を同時に見ていって、異なる文字が現れるケースの内、iのものの方が小さいケースの確率計算すれば求まる。こうして文字列iがjより前に置かれる確率pijがもとまる。
ソートの段階である文字列は他のすべての文字列と比べられるので、iがj以外の他の文字列より前に来る確率を計算して足しあわせれば、iの現れる位置の期待値というのは求まることになる。

以下ソース。

class StrangeDictionary {
public:
  vector <double> getExpectedPositions(vector <string> words) {
    int N = words.size();
    vector<double> ret(N, 0);
    
    for(int i = 0; i < N; i++){
      for(int j = i + 1; j < N; j++){
	double a = 0, b = 0;
	for(int k = 0; k < (int)words[i].length(); k++){
	  if(words[i][k] > words[j][k]) a++;
	  if(words[i][k] < words[j][k]) b++;
	}
	ret[i] += a / (a + b);
	ret[j] += b / (a + b);
      }
    }
    return ret;
  }
};