Codeforces #468 Div1 B. Game with String

こちらはBとして普通の難易度。
http://codeforces.com/contest/930/problem/B

問題

N文字の文字列Sが与えられる。
この文字列を0～(N-1)文字だけ等確率でrotateさせたとする。
ただし何文字rotateしたかは教えてもらえない。

その状態で先頭の文字を与えられたとする。
そしてもう１か所位置を任意で選択し、その位置の文字を知ることができるとする。
最適な行動をとったとき、rotateした文字数を当てられる確率を求めよ。

解法

まずrotate後の文字列を先頭文字ごとに分類し、それぞれにおいてrotateした文字数を当てられる確率を求めよう。
先頭が一致するrotate後の各文字列について、各位置における各文字の登場頻度を求めておこう。
各位置に着目したとき、1回とか登場しない文字が多い位置を選択するのが最適なので、それを求めればよい。

int N;
string S;

int mask[26][5050][26];
int cnt[26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) {
		x=S[i]-'a';
		cnt[x]++;
		FOR(j,N-1) {
			mask[x][j][S[(i+j+1)%N]-'a']++;
		}
	}
	
	int win=0;
	FOR(i,26) {
		int best=0;
		FOR(j,N) {
			int tot=0;
			FOR(x,26) if(mask[i][j][x]==1) tot++;
			best=max(best,tot);
		}
		win+=best;
		
	}
	_P("%.12lf\n",win*1.0/N);
	
}

まとめ

上のコードの計算量はO(N^2+(N*w^2))だけど、O(N^2*w)でも通るっぽいな。