Codeforces #673 Div1 A. k-Amazing Numbers

いつもに比べDiv1の割に簡単だったようで、4完したけどそこまで順位が良くなかった。
https://codeforces.com/contest/1416/problem/A

問題

整数列Aについて、k-Amazing Numberとは、Aにおけるあらゆる長さkの連続部分列において登場する値のうち最小値である。
k=1～|A|に対し、k-Amazing Numberを求めよ。

解法

Aを値毎に分類する。
各値vについて、登場位置の間隔の最大値がsの時、k≧sであればvがk-Amazing Numberになるうる。
あとはそれらの最小値を答えればよい。

int T;
int N,A[303030];
int D[303030];
vector<int> P[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			P[i+1].clear();
		}
			
		FOR(i,N) {
			cin>>A[i];
			P[A[i]].push_back(i);
			D[i+1]=999999;
		}
		for(i=1;i<=N;i++) if(P[i].size()) {
			int ma=max(P[i][0]+1,N-P[i].back());
			FOR(j,P[i].size()-1) ma=max(ma,P[i][j+1]-P[i][j]);
			D[ma]=min(D[ma],i);
		}
		
		for(i=1;i<=N;i++) {
			if(i>1) D[i]=min(D[i],D[i-1]);
			if(D[i]==999999) cout<<-1<<" ";
			else cout<<D[i]<<" ";
			
		}
		cout<<endl;
	}
}

まとめ

特にコメントのしようもない問題だな…。