Hatena::ブログ(Diary)

skyのaozora日記

2010-04-10

Topcoder Marathon Match58

| 22:42

何かブログ新しく作ったのに何も書かずに放置してたので、Marathon Matchが終わったということで折角の機会だから参加記を書いてみることに。

問題

p-aからp-bの間に素数がx個ある出来るだけ小さな素数pを求めよ

1<=x<=500 4x<=a,b<=25x

初日(3月25日)

問題読む。いつもと違って問題文がめっちゃ短くて英語が苦手な自分にとっては助かる。

それにしても何このガチ数学ゲー!?ちょっとしたスコアを取れる方法すら思いつかずしょっぱなから諦めムードが漂う

5日目(3月29日)

とりあえず何かしないとしゃーないと思って素数を小さい方から調べていく方法で提出。すると思いのほかいい順位が取れてる。29.00で集団の中に。

7日目(4月1日)

どうせ数字が大きくなるほど素数の密度は薄くなるんだろ、と思って二分探索的に調べることに。具体的には、まずmまでの素数をすべて列挙する。そして[0,m^2]の中から数字を選んで、その数字からn個をエラトステネスの篩にかけて、その範囲の中で「p-aからp-b(pは素数)の間にある素数の数の最小値」を調べ、それがxより大きいか小さいかで調べる範囲を絞っていく感じ。しかしスコアはあまりあがらず34点台。

8日目(4月2日)

上の方法でmとnの調整してみたらそれなりにスコアが上がった。40点台後半。

9日目〜最終日(4月3日〜4月7日)

素数の密度は必ずしも単調減少しているわけではなく、ある範囲に素数がk個あった時、同じ範囲の大きさでそこより数字が小さい部分にある素数はk個以下かもしれないのに、上の方法ではそれをルーズしているから、単純な2分探索ではなく焼きなまし的に柔軟に範囲を狭めていく方法を考えたけど、大学のオリ合宿+ガイダンス+授業開始でこっちまで頭が回らず。

最終結果

暫定得点47.71 暫定順位55/376

書いたコードの短さ&費やした時間の短さ&アイデアの単純さの割にはそれなりにいい順位が取れた気がするwしかしhttp://topcoder.g.hatena.ne.jp/chokudai/20100409/1270782745(chokudaiさん)やid:tomerunさんの参加記を見て上位を取る人はやることが全然違うなと実感。マラソンは本番中より他の人の参加記を読む方が勉強になりますよね。アトキンの篩とかMiller-Rabin法とか、解を探す基準になる数をコードに埋め込むとか。自分も少しずつ成長していきたいです。

トラックバック - http://d.hatena.ne.jp/skyaozora/20100410/1270906958