Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-05-27SRM471 Div1

SRM471 Div1 250 PrimeSequences

| 00:50 | SRM471 Div1 250 PrimeSequences - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM471 Div1 250 PrimeSequences - SRM diary(Sigmar) SRM471 Div1 250 PrimeSequences - SRM diary(Sigmar) のブックマークコメント

素数を2で割って余りを切り捨てると、また素数になるような数を考えます。さらにその素数を2で割って余りを捨て、ということを素数でなくなるまで続けます。このようにして生成される素数の列について、N以下の数でD個以上の素数を生成できる最大の数を求める問題です。

2<=N<=10000000、1<=D<=10


最初Nが100万に見えて、エラトステネスの篩で楽勝だなと思ったのですが、よく見ると1000万だったので、TLEするなあ、やはりそんな簡単なワケないか・・と考えました。(←間違い、というか記憶違い・・・そんな簡単でした)

難しいなあと思っていたら、みんなぽんぽん提出しているので、何か簡単に解く方法を見落としているに違いないと思い・・・

色々試してみると、Dが最大10となっているけど、N以下で1桁でない数のうち、

  • 1の位が偶数か5の場合は素数ではなく、
  • 1,3,7の場合は5回以下で循環するため、

1の位が9でない限りDは最大5になるようでした。

この分だと9のときでもDが6以上になる場合はほとんどなさそうだなと思い、定義通りに実装したプログラムでローカルで走らせてみると、予想通り6のときはほとんど解がなく、7以上で答えなしとなりました。

解の算出に時間がかかるのはD>=5の場合だけなので、この場合だけ埋め込みをしてしまえば2秒以内は余裕そうです。という感じで頑張って書いてコンパイルしようとしたあたりでサーバー様がお亡くなりになりました。

本番で提出できなかったのは残念ですが、いずれにせよすでに50分ほど経過しており、ひどい成績になってしまったのである意味ラッキーでした。

ソースは下のほうに載せます(解1)。


本番が終わってから、埋め込みなどしなくても解けるもっと効率的な方法に気づきました。

定義では素数を2で割っていきますが、生成する素数の列を逆方向に作ることもできます。その場合、2をかけて1を足すことを繰り返すことになります。

そうすると、Nが1000万、Dが10のときでも、解の候補は1000万/(2^10)で1万くらいになるので、だいぶ計算が余裕になります(解2)。


さらに今日みなさんのブログを見ると、普通に篩で解けたようで・・・。何か、一度はまると抜け出せないですね。。篩で間に合うということはまさかないだろうと思い込んでしまってました。篩で解いたソースも書いたので載せておきます(解3)。

  • 解1(埋め込み)
class PrimeSequences {
public:
	int getLargestGenerator(int N, int D) {
		int result=-1;
		int tmp, cnt;
		bool flag;

		if(D>6) return -1;
		if(D==6) {
			if(N>=4068479) return 4068479;
			if(N>=2029439) return 2029439;
			if(N>=2879) return 2879;
			return -1;
		}
		if(D==5) {
			if(N>=9717119) return 9717119;
			if(N>=9511199) return 9511199;
			if(N>=8624159) return 8624159;
			if(N>=7145759) return 7145759;
			if(N>=6753119) return 6753119;
			if(N>=6484319) return 6484319;
			if(N>=5454719) return 5454719;
			if(N>=4737599) return 4737599;
			if(N>=4288799) return 4288799;
			if(N>=4068479) return 4068479;
			if(N>=3301919) return 3301919;
			if(N>=2978399) return 2978399;
			if(N>=2683679) return 2683679;
			if(N>=2297759) return 2297759;
			if(N>=2034239) return 2034239;
			if(N>=2029439) return 2029439;
			if(N>=1067999) return 1067999;
			if(N>=1014719) return 1014719;
			if(N>=982559) return 982559;
			if(N>=861599) return 861599;
			if(N>=858239) return 858239;
			if(N>=2879) return 2879;
			if(N>=1439) return 1439;
			if(N>=47) return 47;
			return -1;
		}
		//Nが4以下の場合は定義通りに解く
		for(int i=N; i>=2; i--) {
			tmp=i; cnt=0;
			while(tmp>=2) {
				flag=true;
				for(int j=2; j*j<=tmp; j++) {
					if(tmp%j==0) {
						flag=false;
						break;
					}
				}
				if(!flag) {
					break;
				}
				cnt++;
				if(cnt>=D) {
					result=i;
					break;
				}
				tmp/=2;
			}
			if(result>0) break;
		}

		return result;
	}
};
  • 解2(逆順に素数列を生成)
class PrimeSequences {
public:
	int getLargestGenerator(int N, int D) {
		int tmp, n;
		bool flag;

		//Nを2^(D-1)で割る
		n=N>>(D-1);
		//素数列を逆順に生成
		for(int i=n; i>=2; i--) {
			tmp=i; flag=false;
			for(int j=0; j<D; j++) {
				flag=false;
				for(int k=2; k*k<=tmp; k++) {
					if(tmp%k==0) {
						flag=true;
						break;
					}
				}
				if(flag) break;
				tmp=tmp*2+1;
			}
			if(!flag && tmp/2<=N) return tmp/2;
		}

		return -1;
	}
};
  • 解3(エラトステネスの篩)

memset(vn, true, sizeof(vn))というのは良いのかな・・・

手元の環境ではvnにtrueが代入されますが、環境依存でうまくいかないことはないんだろうか。。。

class PrimeSequences {
public:
	int getLargestGenerator(int N, int D) {
		int tmp;
		bool vn[10000010];
		bool flag;

		//篩による素数生成
		memset(vn, true, sizeof(vn));
		vn[0]=vn[1]=false;
		for(int i=2; i*i<=N; i++) {
			if(!vn[i]) continue;
			for(int j=i*2; j<=N; j+=i) {
				vn[j]=false;
			}
		}

		//解を算出
		for(int i=N; i>=2; i--) {
			tmp=i;
			flag=true;
			for(int j=0; j<D; j++) {
				if(!vn[tmp]) {
					flag=false;
					break;
				}
				tmp/=2;
			}
			if(flag) return i;
		}

		return -1;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100527