CSAcademy Round #77 : D. Expected Lcp

相変わらずDiv2だけ調子が良い。
https://csacademy.com/contest/round-77/task/expected-lcp/

問題

N個の文字列S[i]が与えられる。
このうち2個の文字列をランダムに等確率で選ぶ場合、LCP長の平均値を求めよ。

解法

2要素選んだ時のLCP長の総和を求め、最後にComb(N,2)で割ろう。

Sをソートしておく。
S[L]～S[R-1]が先頭x文字が等しいとする。
S[L]～S[R-1]を(x+1)文字目が等しいもの毎にグルーピングしよう。
Sは昇順なので、各グループは[L,R)を分割する複数の区間となる。

ある区間を[A,B)とすると、このグループ内から2要素選べば(x+1)文字目が一致することで、その分LCPの総和がComb(B-A数,2)だけ増加する。
あとは「S[A]～S[B-1]が先頭(x+1)文字が等しいとする。」という問題になるのでDFSで再帰的に総和を求めていけばよい。

int N;
string S[1010101];

ll tot;

void dfs(int L,int R,int C) {
	if(S[L].size()<=C) L++;
	if(R<=L+1) return;
	int LL[26],RR[26];
	int i;
	FOR(i,26) LL[i]=1010101,RR[i]=-2;
	for(i=L;i<R;i++) {
		int c=S[i][C]-'a';
		LL[c]=min(LL[c],i);
		RR[c]=max(RR[c],i+1);
	}
	FOR(i,26) if(LL[i]<RR[i]) {
		ll num=RR[i]-LL[i];
		tot+=num*(num-1)/2;
		dfs(LL[i],RR[i],C+1);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	sort(S,S+N);
	dfs(0,N,0);
	
	_P("%.12lf\n",tot/(1.0*N*(N-1)/2));
}

まとめ

同じ問題どっかで出てそう。