yukicoder : No.6 使いものにならないハッシュ

難易度調整等で★３以上になった奴をつぶして行きます。
http://yukicoder.me/problems/24

問題

整数Nのハッシュ値hash(N)とは、Nを(Nの各桁の和)で置き換えるという処理をNが１ケタになるまで繰り返したのちのNの値とする。

整数の閉区間[K,N]中の連続素数列で、互いにハッシュ値が衝突しない最長列を求め、先頭の要素を答えよ。

解法

まず[K,N]中の素数を列挙して、ハッシュ値を求めよう。

後は素数列の各数値を連続素数列の始点とし、どこまで(衝突せず)終点を後ろに伸ばせるかチェックしていけば良い。
ハッシュ値は0～9の何れかなので、始点から終点はせいぜい10要素にしかならないため、実行時間にはだいぶ余裕ができる。

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
int K,N;

// ２回以上行うならNP,prime,divを要クリア
void cprime() {
	int i,j;
	for(i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(j=i;j<prime_max;j+=i) divp[j]=i;
	}
}

int hash(int v) {
	while(v>=10) v=v/10+v%10;
	return v;
}

vector<pair<int,int> > V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	cprime();
	
	cin>>K>>N;
	for(i=K;i<=N;i++) if(divp[i]==i) {
		j=i;
		while(j>=10) j=j/10+j%10;
		V.push_back(make_pair(i,j));
	}
	
	x=y=-1;
	FOR(i,V.size()) {
		int mask=0;
		FOR(j,100) {
			if(i+j>=V.size()) break;
			if(mask & (1<<(V[i+j].second))) break;
			if((j+1)>=y) x=V[i].first,y=j+1;
			mask |= 1<<(V[i+j].second);
		}
	}
	
	
	_P("%d\n",x);
}

まとめ

最近のyukicoderの難易度を見てると、★３にしては簡単かも。