Codeforces #254 Div1 B. DZY Loves FFT

これは本番かなり順当に思いつけた。
http://codeforces.com/contest/444/problem/B

問題

1～Nのpermutationとなっている数列A[i]と、0,1で構成される数列B[i]がある。
C[i]=max(A[j]*B[i-j]) (j<=i)で定義されるC[i]を求めよ。

なお、A,Bは疑似乱数を用いて生成され,B[i]のうちD個が1である。

解法

C[i]は数式こそA[j]*B[i-j]だが、B[i]は0か1なので、結局B[i-j]が1となるA[j]の最大値を求めるのが問題となる。

• Dが小さい場合
  • B[i]が1となる数はD個以下と絞られるので、そのようなB[i-j]を全探索し、最大のA[j]を探せばよい。この場合O(ND)で処理できる。
• Dが大きい場合
  • Dが大きい場合は、A[j]の大きい順に探せば平均N/D個探索するうちにB[i-j]が1であるjに当たる。この場合O(N^2/D)で処理できる。
  • なかなかB[i-j]が1にならないようなBを意図的に作ることはできるかもしれないが、今回はBが乱数生成のためそこは考えなくてよい。

以下のコードはD=1000を境目とした。

ll N,D,X;
ll A[100001],B[100001];
vector<int> BB;

ll getNextX() {
	return X=(X * 37 + 10007) % 1000000007;
}

void dosmall() {
	int f,i,j,k,l,x,y;
	
	FOR(i,N) {
		ll ma=0;
		FOR(j,BB.size()) if(BB[j]<=i) ma=max(A[i-BB[j]],ma);
		_P("%lld\n",ma);
	}
}

void dolarge(){
	int f,i,j,k,l,x,y;
	int ID[100001];
	FOR(i,N) ID[A[i]]=i;
	
	FOR(i,N) {
		int ok=0;
		for(j=N;j>=N-1000;j--) {
			if(ID[j]>i) continue;
			if(B[i-ID[j]]) {
				_P("%d\n",j);
				ok=1;
				break;
			}
		}
		if(ok) continue;
		ll ma=0;
		FOR(j,BB.size()) {
			if(BB[j]>i) break;
			ma=max(A[i-BB[j]],ma);
		}
		_P("%lld\n",ma);
	}
	
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>D>>X;
	FOR(i,N) A[i]=i+1;
	FOR(i,N) swap(A[i],A[getNextX()%(i+1)]);
	FOR(i,N) B[i]=(i<D);
	FOR(i,N) swap(B[i],B[getNextX()%(i+1)]);
	FOR(i,N) if(B[i]) BB.push_back(i);
	
	if(D<=1000) dosmall();
	else dolarge();
}

まとめ

数列生成に乱数を使う場合、極端に偏った構成がないことを前提に出来るので、Codeforcesならそこを疑うべきだね。
TopCoderは単純に巨大数列を作るために乱数生成を使うので油断できないけど…。