Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-05-10Marathon Match 58/59

Marathon Match 58

| Marathon Match 58 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - Marathon Match 58 - hama_DU@TopCoderへの道

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

連続した自然数の中で、素数の出現率が薄いところを見つける問題。


とりあえず

ある素数が x-isolated であるか判定するプログラムを書き、

それを2から順番に回してみる。

しかしこれだと xが小さい場合や、 a + b が大きくなる場合に

答えが出せなくなってしまう。そこで、求める素数の出現率( x / (a + b) )が

ある一定値以上である場合は先頭から順に探索。

そうでなければ探索開始位置を倍々に増やしながら

10万ずつほど探索するようにしてみた。

これで出したのが22点ちょい/100。


x-isolated判定高速化

ある範囲(p - a <= n <= p + b)の素数の有無を判定したら、

nを1増やす際の素数の数はp + b + 1 が

素数であるかどうかだけわかればよい。

これでだいぶ速くなった。

2から順に探索する場合の範囲を緩めて提出。50点ぐらい/100。


埋め込みを使う

xに対して、a、bを最大にとった場合の答えを埋め込むことにした。

これにより、a、bにどんな値が来ても、答えは必ずその数以下となるし、

なにより答えが出せずに0点ということがなくなる。

以降はアルゴリズムの改良と同時に、

なるだけ小さい値の埋め込みデータの探索にいそしんだ。

結果は51点ぐらい/100だった。


エラトステネスの篩で素数テーブル生成

をすることにした。

範囲を限定して数が素数であるかどうかを

あらかじめ求めておくというアイデア。

しかしメモリの使用制限があるため、

生成できるテーブルの大きさは512M。

探索範囲を倍々に増やす場合は、

まず512Mの素数判定テーブル生成

→その範囲で順繰り探索

→次のテーブル生成...

という処理を繰り返すようにしてみた。

テーブル生成に2sほど時間がかかるのがネックだが、

あてずっぽうにやるよりかはいいはずだ。

これで提出!52点!ヽ(・ω・)/ ズコー


そして

ひたすら埋め込みデータを作成。

がんばったけど点数は一向に上がらなかった。


結果

480点!48位/375。まぁそこそこか。

これで初回ということもありratingが黄色になりました。(1200→1578)わーい