Codeforces #289 Div2 E. Pretty Song

これもCより楽な気がする。
http://codeforces.com/contest/509/problem/E

問題

文字列のsimple prettinessとは、文字列中に含まれる母音の割合である。
文字列のprettinessとは、文字列の全部分文字列におけるsimple prettinessの和である。

N文字の文字列Sが与えられたとき、prettinessを答えよ。

解法

(0-indexで)i文字目S[i]が母音だとすると、S[L..i..R]となる部分文字列にS[i]が含まれ、各部分文字列のsimple prettinessに1/(R-L+1)だけ貢献する。
よって0≦L≦i≦R＜NとなるL,Rに対し1/(R-L+1)の和を取ればよい。

• L=iの時、R=i,i+1,...に対し1/(R-L+1)は1/1,1/2,1/3,...,1/(N-i)
• L=i-1の時、R=i,i+1,...に対し1/(R-L+1)は1/2,1/3,1/4,...,1/(N-i+1)

...

• L=0の時、R=i,i+1,...に対し1/(R-L+1)は1/(i+1),1/3,1/4,...,1/N

この値は、、で定義したG(x)を事前に準備しておくと、G(N)-G(N-(i+1))-G(i)で求めることができる。

string S;
int L;
double revsum[505000];
double revsum2[505000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S;
	L=S.size();
	
	double ret=0;
	for(i=1;i<=500000;i++) revsum[i]=revsum[i-1]+1.0/i,revsum2[i]=revsum2[i-1]+revsum[i];
	
	FOR(i,L) {
		if(strchr("IEAOUY",S[i])) {
			x=max(i+1,L-i);
			ret += revsum2[L]-revsum2[L-x]-revsum2[x-1];
		}
	}
	_P("%.12lf\n",ret);
}

まとめ

文字ごとに最終的な結果に貢献する値を求める、割と定番な問題。