kmjp's blog

競技プログラミング参加記です

TopCoder SRM 542 Div1 Medium StrangeDictionary2

解き方はすんなり思いついたけど計算量の見積もりが甘かった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11935

問題

L文字の異なる文字列N個をソートしたい。
普通、文字列のソートは先頭から順に文字を比較する。
しかしここでは1~Lのpermutationであるp[i]を考え、その位置順で文字を比較して文字列をソートする。

p[i]は全permutationのうち等確率で1個選択されるとすると、各文字列がソート後先頭に来る確率を答えよ。

解法

比較過程において、文字列同士が一旦p[i]文字目で差がつくと、p[i+1]以降の文字はどうであっても良い。
よって、各文字列に対し、「まだこの文字列より前に来ることが確定していない」という他の文字列をbitmaskで管理し、「次にx番目の文字で比較すると、残された文字列との大小関係がどうなるか」を求めて行けばよい。

厳密にはこのDPの計算量はO(N^2*L*2^N)かかり、TLEするがbitmaskの処理を単一int型に落とし込むことでO(N*L*2^N)にしている。

class StrangeDictionary2 {
	public:
	int N,L;
	vector<string> W;
	
	double dfs(int cur,int mask) {
		if(dp[cur][mask]>=0) return dp[cur][mask];
		if(__builtin_popcount(mask)==1) return dp[cur][mask]=1;
		dp[cur][mask]=0;
		int pat=0,x,i;
		FOR(i,L) {
			if(ngmask[i] & mask) pat++;
			else if((samemask[i] & mask)!=mask) pat++, dp[cur][mask]+=dfs(cur,samemask[i] & mask);
		}
		if(pat==0) return dp[cur][mask]=0;
		return dp[cur][mask]/=pat;
	}
	
	vector <double> getProbabilities(vector <string> words) {
		W=words;
		N=W.size();
		L=W[0].size();
		
		int i,j,x,y;
		FOR(i,16) FOR(j,1<<16) dp[i][j]=-1;
		vector<double> V;
		FOR(i,N) {
			FOR(x,L) {
				ngmask[x]=samemask[x]=0;
				FOR(y,N) ngmask[x] |=(W[y][x]<W[i][x])<<y;
				FOR(y,N) samemask[x] |=(W[y][x]==W[i][x])<<y;
			}
			V.push_back(dfs(i,(1<<N)-1));
		}
		return V;
		
	}
}

まとめ

解き方はともかく、TLEが厄介。