Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/04/10

Marathon Match 58 IsolatedPrimes

| 00:55

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14226&pm=10844

HandleScoreRankLast Submission TimeLanguageExample TestsSubmissions
yuyarin23.0016203.26.2010 13:10:23C++42

はじめての MM で SRM と勝手が違って若干戸惑った.

とりあえず素数を最初から舐める方法で実装してみたけど,解が大きい場合に簡単にTLEしてしまう.pi関数と二分探索で解になる素数の位置の当たりをつけて MR 法で素数判定するコードも書いてみたけど,役に立たなかった.

コードサイズを考えると,きっとオフラインで計算したデータを持っておくのかなと思ったけど,何をどう持ってどういうアルゴリズムにするのかを思いつかなくて,年度初めで忙しくなってきて断念.結局最初に書いたコードで submit.

高速化のために若干可読性は落ちているけど,アルゴリズムは多分解説が要らないほど単純なコードだと思う.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;
typedef unsigned long long ull;
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define N 100000000

// 素数の配列 primes[0]=2, primes[1]=3, ...
ull primes[N]; 
// [primes[i]-a, primes[i]+b] に含まれる素数の個数の配列
unsigned int counts[N]; 

// primes[], counts[] のインデックス
unsigned int n=0;

// インデックス n の探索範囲の下界
unsigned int start=0;

int x, a, b;

class IsolatedPrimes
{
public:

bool isPrime(ull m)
{
	ull max = (ull)sqrt(m+1);
	// 2, 3 は調べなくて良い
	for(unsigned int i=2; i<n && primes[i]<=max; i++)
	{
		if(m%primes[i]==0) return false;
	}
	return true;
}

ull f(ull p)
{
	if(!isPrime(p)) return 0;
	
	n++;
	primes[n] = p;
	counts[n] = 1;
	
	// primes[n]-a より小さい素数はチェックしない
	for(unsigned int i=start; i<n; i++)
	{
		// primes[i] が primes[n]-a 〜 primes[n] に含まれる
		// => counts[n] += 1;
		unsigned int fa = (p <= a + primes[i]);
		counts[n] += fa;
		
		// primes[n] が primes[i] ~ primes[i]+b に含まれる
		// counts[i] += 1;
		unsigned int fb = (p <= b + primes[i]);
		counts[i] += fb;
		
		// primes[i] が primes[n]-a よりも小さくなった
		// => 探索対象から外れた
		if(!(fb|fa))
		{
			// primes[i] 中心の範囲に含まれる素数の個数 counts[i] をチェック
			if(counts[i]<=x && primes[i]>(ull)a) 
			{
				return primes[i];
			}
			// 調べる必要がなくなった
			start = i+1;
		}
	}
	
	return 0;
}

string findPrime(int x_, int a_, int b_)
{
	x = x_; a = a_; b = b_;
	
	primes[0] = 2; primes[1] = 3;
	counts[0] = 2; counts[1] = 2;
	
	n = 1;
	
	ull max = ((1ull<<63)-1-b)/6;
	ull ans = 0;
	
	// 素数は 6*i±1 で表現できる
	for(ull i=1;i<max;i++)
	{
		if((ans=f(6*i-1))>0) return tos(ans);
		if((ans=f(6*i+1))>0) return tos(ans);
	}
	
	return "0";
}
};

int main(int argc, char* argv[])
{
	IsolatedPrimes ip;
	if(argc>=4)
	{
		cout << ip.findPrime(atoi(argv[1]),atoi(argv[2]),atoi(argv[3])) <<endl;
	}
	return 0;
}