■ [MM]Marathon Match58 
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14226&pm=10844
第58回記念（?）で参加者数が爆発していた
問題
整数x,a,bが与えられる。1<=x<=500, 4x<=a,b<=25x。
[p-a, p+b]の範囲に素数がx個以下しか存在しないようなできるだけ小さい素数pを見つけろ、という問題。
ざっくり言うと「素数が薄いところを探せ」。
単純な探索
まず素数定理から解の上限がわかるので、そこからスタート。
順番に素数を生成して、一定時間解を探す。解が見つかったらスタートする値を1/2に、見つからなかったら1.1倍に、みたいな感じで探索する位置を変えつつ解を探す。
これで31pt。
最初の実装では横着してjava.math.BigInteger.nextPrime()とか使ってて遅かったので、Miller-Rabinテストを自前で実装すると素数生成がだいぶ早くなった。44ptに上昇。
イージーケース特殊化
x,a,bが小さいときは答えが小さい範囲で収まるので、上の方法みたいに順次探索しなくても一番小さいところから順に素数生成して調べれば最適解が見つかる。
なので、xが小さかったり、素数定理から求めた解の上限が一定のしきい値以下だったりした場合は、エラトステネスのふるいで素数を生成して全探索する。
エラトステネスのふるいに自明な最適化を入れていくと、5億までの素数を列挙するのがサーバー上で14秒。全探索する値の見極めはそのあたりで。
java.util.BitSetって微妙にマイナーだけどけっこう便利です。
ここで47pt。
高速化（泥沼）
パッとした方法も思いつかないので、がんばってたくさん探索できるようにしないとなぁと考えて高速化し始める。
- Miller-Rabinテスト部分（ボトルネック）
- 順番に素数生成して調べる箇所
- BitSetを自前で実装
- 手元では1割くらい早くなったがサーバー上では変わらず
- System.currentTimeMillis()の呼び出し削減
といろいろやったけれどスコアには影響なし…
今回もまた「ボトルネックじゃないとわかっていても最適化したくなる」に負けた
埋め込み（泥沼）
ソースコードのサイズ上限が100KBなのである程度の埋め込みができる。
x,a,bを一定間隔で区切って、手元でじっくり時間をかけて探索させて出た答えを良い上限として使うことができないか、と考えた。
その方針で数十時間計算させてみたが、埋め込めるくらいの量のx,a,bの分割粒度では、良くて厳密解の10倍程度の上限しか与えられなさそうだった。
これでは意味がない。没
埋め込み（当たり）
これまでにいろいろ計算させた結果を眺めてみると、解には同じような値が何度も出ていることがわかる。
これはつまり、解は素数が薄いところに集中するということなので、そのような場所を探せば良い。
というわけで、「ある素数とそのx個後の素数ができるだけ離れているところ」を探してやった。
小さい数から見ていって、この離れ具合の最大値が更新された位置を記録していく。
もちろん1から2^63まで全部調べるのは無理なので、
- とりあえず10^11くらいまでは全部やる
- それ以上の範囲は、
- [2*10^11, 2*10^11+10^8]、[4*10^11, 4*10^11+10^8]、[8*10^11, 8*10^11+10^8]、…
- みたいに、一定の倍率で開始位置を大きくしつつ一定幅の区間を調べた
- この例では2倍ずつやっていますが実際は1.1倍ずつ
- xを1から500まで全部調べると、計算時間的にも埋め込み可能サイズ的にも足りないので、5刻みで
これによって「素数が薄いところ」が見いだせるので、コード内に埋め込んで、その位置だけを調べるようにした。
この戦略は有効だったようで、80pt台後半まで持って行けた。
概算では92,3ptくらい行けるかと思っていたがそこまで伸びなかった。ということは、上位の人たちの戦略にはもう一段階何かある感じ
それか、Miller-Rabinテストをルーズに行ったせいでの誤判定が意外と効いちゃってたというのもあるかも
結果
この問題では厳しいかと思っていたけれど、何とかレーティング上昇圏に入れました。
今回もまた、これまでに経験したことのないタイプの問題で（実験数学ゲー？）なかなか面白かったです。
終盤になるまで有効な方針が思いつかず冷や冷やものでしたが見つかって良かった。粘って考えてみるものだ。
しかしいつも10位前後なのでこのままではいつまで経っても赤になれないなぁ…
