SRM 542 Div2 950pt : StrangeDictionary

問題概要

長さL(<50)の互いに異なる文字列がN(<50)個ある。ある長さLの置換σを適当に決めて、すべての文字列の順序を置換する。置換した後の文字列をソートしたとき、各文字について何番目の位置に配置されるかの期待値を求める問題。

解法

一瞬Div 1 500の類題より難しいように見えたけど気のせい。各文字列について、何番目に来るかの期待値=前にくる文字列の個数の期待値。お馴染みの線形性を用いると、各文字列が前に来る確率を足しあげればよいことがわかる。文字列A、Bでどちらが前に来るかは、同じ位置で異なる文字を調べると簡単に計算できる。

acceptされたコード

#include <vector>
#include <string>
using namespace std;

struct StrangeDictionary {

	vector <double> getExpectedPositions(vector <string> words) {
		const int N = words.size();
		const int L = words[0].length();

		vector<double> ret(N, 0.0);

		for(int i=0; i<N; ++i){
			for(int j=0; j<N; ++j)if(i!=j){
				int a = 0, b = 0;
				for(int k=0; k<L; ++k){
					if(words[i][k] < words[j][k]){
						++a;
					}
					else if(words[i][k] > words[j][k]){
						++b;
					}
				}
				ret[i] += (double)b / (a + b);
			}
		}

		return ret;
	}

};