Codeforces #351 Div1 A. Bear and Colors

相変わらずConvex Hull Trick苦手でレートを落とした。
http://codeforces.com/contest/674/problem/A

問題

N個のボールが並んでおり、それぞれの色はT[i]である。
連続したボールの部分列に対し、登場回数が最多の色をdominantであるとする(同着の場合色番号の若い方が優先)。
N*(N+1)/2通りの部分列の組み合わせに対し、各色がdominantとなる回数を求めよ。

解法

部分列の左端を定め、右端を１つずつ伸ばしながら各色の登場回数を数えていけばO(N^2)で済む。

int N;
int T[5050];
int cnt[5050];
int R[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	
	FOR(x,N) {
		FOR(i,N+1) cnt[i]=0;
		int ma=0,id=0;
		for(y=x;y<N;y++) {
			r=T[y];
			cnt[r]++;
			if(cnt[r]>ma) ma=cnt[r],id=r;
			else if(cnt[r]==ma && r<id) id=r;
			R[id]++;
		}
	}
	
	FOR(i,N) _P("%d%s",R[i+1],(i==N-1)?"\n":" ");
}

まとめ

O(N^2*logN)解は少し丁寧にやらないとTLEするようだ。