Codeforces ECR #028 : F. Random Query

遠回りな回答をしてしまった。
http://codeforces.com/contest/846/problem/F

問題

N要素の数列Aに対し、２値L,R∈[1,N]を当確率で選ぶ。
L＞Rの場合はL,Rを反転させよう。
この時A[L...R]登場するユニークな要素数の期待値を求めよ。

解法

左端Lに対し、各L≦R≦NのRのユニークな要素数の総和を数えていこう。
A[L...R]中ある数値xが最初に登場する位置がA[f(x)]=xだとする。
するとRがf(x)以上の場合にxによってユニークな要素数が1増えるので、全体で(N+1-f(x))通りだけ1増加する。
Lを固定したとき、このf(x)の総和が全体の値に加算される。

まずL=1の場合におけるf(x)をすべて求めておこう。
以後、Lをインクリメントする際のf(x)の総和の変化を考える。
インクリメント前にf(x)=Lだったxについて、f(x)はLの次に値xを持つ要素、例えばf(x)=next(L)とする。
そうするとf(x)の総和はnext(L)-Lだけ変化する。

int N;
int A[1010101];
int nex[1010101];
int pos[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&A[i]);
	
	FOR(i,1010001) pos[i]=N;
	for(i=N-1;i>=0;i--) {
		nex[i]=pos[A[i]];
		pos[A[i]]=i;
	}
	
	ll tot=0;
	ll sum=0;
	FOR(i,1010000) sum+=N-pos[i];
	
	FOR(i,N) {
		tot+=sum-1;
		sum-=nex[i]-i;
	}
	double pat=1.0*N*(N-1)/2.0;
	_P("%.12lf\n",(tot*2+N)/(1.0*N*N));
	
}

まとめ

もっと簡単な解法を取ってる人も多かった。