Codeforces #429 Div1 D. Destiny

うーむ残念。
http://codeforces.com/contest/840/problem/D

問題

N要素の数列Aに対し、以下のクエリQ個に答えよ。

• 整数L,R,Kが与えられる。数列A[L...R]のうち、(R-L+1)/K回以上登場する要素のうち最小値を答えよ。

解法

乱択でpretestは通ったが本番は通らなかった。
最終的に別解で解いたが一応紹介。

Kは最大で5と小さい。
よってA[L...R]からランダムに要素を選べば、1/5以上の確率で真の解にヒットする。
言い換えればn回乱択を行えば(4/5)^nの確率でヒットするので、nが十分大きければよい。
…ただ残念ながら計算時間の考えてn=60程度までしか増やせず、何度か試したが正解できなかった。

そこで平方分割で対応した。

• R-Lが十分小さい(D以下)の場合:
  • A[L...R]を愚直に数え上げる
• R-Lがある程度以上大きい(D以下)の場合:
  • 解xがあるとすると、そもそもA中でD/K回以上登場していなければならない。そのような数xはA中で高々(NK/D)通りしかない。
  • よって登場回数がNK/D以上の数xについては先に全クエリにおいてA[L...R]中に(R-L+1)/K回以上登場するか数えておけばよい。

int N,Q;
int A[303030];
int L[303030],R[303030],K[303030];
int ret[303030];
vector<int> V[303030],sm,la;
int cnt[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,N) {
		scanf("%d",&A[i]);
		V[A[i]].push_back(i);
	}
	FOR(i,Q) {
		scanf("%d%d%d",&L[i],&R[i],&K[i]),L[i]--,ret[i]=-1;
		if(R[i]-L[i]>=2500) la.push_back(i);
		else sm.push_back(i);
	}
	FOR(i,N+1) if(V[i].size()>400) {
		FORR(j,la) if(ret[j]==-1 && V[i].size()>(R[j]-L[j])/K[j]) {
			x = lower_bound(ALL(V[i]),R[j])-lower_bound(ALL(V[i]),L[j]);
			if(x>(R[j]-L[j])/K[j]) ret[j]=i;
		}
	}
	
	FORR(r,sm) if(ret[r]==-1) {
		x=(R[r]-L[r])/K[r];
		for(j=L[r];j<R[r];j++) {
			cnt[A[j]]++;
			if((ret[r]==-1 || ret[r]>A[j]) && cnt[A[j]]>x) ret[r]=A[j];
		}
		for(j=L[r];j<R[r];j++) cnt[A[j]]--;
	}
	
	FOR(i,Q) _P("%d\n",ret[i]);
}

まとめ

乱択いいと思ったんだけどな。K≦4なら行けたのかな。