kmjp's blog

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

TopCoder SRM 742 Div1 Medium RandomConcat

うーん、これは典型っぽいな…。
https://community.topcoder.com/stat?c=problem_statement&pm=15228

問題

文字列集合Sと、文字列Tが与えられる。
Sを等確率でランダム順に並べて連結してできる文字列において、Tが部分列として登場する回数の期待値を求めよ。

解法

dp(0,0)から初めて、以下を順次求めていこう。
dp(mask,s) := Sのうちmaskに示す要素を並べてできた文字列のうち、最大でsuffix s文字とTのprefix s文字が一致するような状態になる確率

dp(mask,s)に対し、maskに未登場の文字列をSから当確率で選び、どう状態遷移するかをKMP法の要領で求めていけばよい。

int N,L;
double dp[1<<15][55];
int table[16][55];
int num[16][55];
string S;

class RandomConcat {
	public:
	void create_table(int id,string T) {
		
		for(int cur=0;cur<=S.size();cur++) {
			string U=S.substr(0,cur);
			FORR(t,T) {
				U+=t;
				while(U.size()>S.size()) U.erase(U.begin());
				while(U!=S.substr(0,U.size())) U.erase(U.begin());
				if(U.size()==S.size()) num[id][cur]++;
			}
			table[id][cur]=U.size();
		}
		
	}
	
	double expectation(vector <string> pieces, string needle) {
		N=pieces.size();
		S=needle;
		int i,j;
		ZERO(table);
		ZERO(num);
		FOR(i,N) create_table(i,pieces[i]);
		
		double ret=0;
		ZERO(dp);
		dp[(1<<N)-1][0]=1;
		for(int mask=(1<<N)-1;mask>0;mask--) {
			FOR(i,S.size()+1) if(dp[mask][i]>0) {
				double cand=dp[mask][i]/__builtin_popcount(mask);
				FOR(j,N) if(mask&(1<<j)) {
					ret+=cand*num[j][i];
					dp[mask^(1<<j)][table[j][i]]+=cand;
				}
			}
		}
		
		
		return ret;
	}
}

まとめ

Codeforcesっぽい。