TopCoder SRM 769 : Div1 Easy Div2 Hard PrimePruning

せっかくHighest近かったのにEasy落としてレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=15755

問題

素数の先頭N個を並べた数列において、値pを((p % 26)+1)番目のアルファベットに置き換えた文字列Sを考える。
このうちE箇所の文字を消して作れる文字列のうち、辞書順最大の物を求めよ。

解法

Eが大きく、N-Eが1000以下なのがポイント。
Nが十分大きい場合、Sを構成する文字列のうち1/13個程度は'z'なので、Nが20000以上あるなら'z'を(N-E)個並べたものを答えればよい。
よって以後N≦20000の場合を考える。

とはいえ、あとは辞書順最大の文字列を探す問題なので、現在位置から最寄りのa～zの登場位置を覚えておき、残り消せる文字列の範囲内で到達できる最大のアルファベットを貪欲に探せば終わり。

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int nex[20202][26];

class PrimePruning {
	public:
	string maximize(int N, int E) {
		cprime();
		int x;
		if(N>=20000) return string(N-E,'z');
		int i,j;
		
		FOR(i,26) nex[N][i]=N+1;
		for(i=N-1;i>=0;i--) {
			FOR(j,26) nex[i][j]=nex[i+1][j];
			nex[i][prime[i]%26]=i+1;
		}
		
		string R;
		int cur=0;
		int del=E;
		while(cur<N) {
			if(N-cur==del) break;
			for(i=25;i>=0;i--) {
				if(nex[cur][i]-1-cur<=del) break;
			}
			R.push_back('a'+i);
			del-=nex[cur][i]-cur-1;
			cur=nex[cur][i];
		}
		
		
		return R;
		
	}
}

まとめ

何を勘違いしたか、Nが大きいときyを(N-E)個並べてしまった。