Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-04-09

MarathonMatch58参加記その1

| 12:12 | MarathonMatch58参加記その1 - chokudaiの日記 を含むブックマーク はてなブックマーク - MarathonMatch58参加記その1 - chokudaiの日記 MarathonMatch58参加記その1 - chokudaiの日記 のブックマークコメント

Marathon Matchが終わったので参加記を

問題内容

範囲[1,500]のxと、範囲[4x,25x]のa,bが与えられる。p-aからp+bの間に素数がx以下となるpのうち、出来るだけ小さいものを返せ。それぞれのケースに対し「(全体最小の答え)/(自分の答え)」が点数となり、これの和を出来るだけ大きくする。

最初に考えること(open-submit6)

素数問題だなぁ、って思ってうげーってなる。素数はあんまり詳しくない。ということで検索に徹する。

このあたりを適当に調べて、それぞれ実行してみる。新規の知識ってのは結構役に立つことが多いんだけど、安易に使うと死ぬので、本当に役に立つかどうかをきちんと見極めるのが大切。

エラトステネスの篩
  • 高速に連続した範囲の素数を列挙することが出来る。
  • 1から篩っていくことが多いが、頭の素数列があれば途中だけ篩うのも可能(区間篩いっていうのかな)
アトキンの篩
  • エラトステネスよりちょっと早い
  • 正直仕組みがいまいち把握できてなかったので、途中だけ篩えるかは判らず
ミラーラビン素数判定法
  • やたらでかい素数に対してもある程度高速に判定できる
  • 難しい判定法だから高速に見えるが、ぶっちゃけ素数列挙に関しては遅い 使わないほうが良いかも?
  • たぶん、「ゎぁぃ、ミラーラビンつよい!」とか初心者が引っかかって死にそうだなぁw
素数定理
  • 適当な範囲での素数の存在密度がわかる
  • ということは、「適当な奇数素数である確率」が出るから、「ある1億程度の範囲を探索した際に、答えとなる範囲が存在する確率」がある程度統計的に求まる?

ということで、調査は終了させてとりあえず実装に移る

実装
  • アトキンの篩いで、5*10^7程度まで素数を列挙 そこまでに回答があればそれを提出
  • 見つからなかった場合、素数定理を用いて、適当な1e7の範囲に回答が半分以上存在する部分を二分探索で調べる
    • ・・・のは面倒だったので適当な係数をかけてフィーリングで調節しましたw
  • 調査ポイントを調べたら、適当な1e7の範囲に対して、解が存在するかエラトステネスの篩を用いて調べる。
  • 解が見つからなかったら、今調べてる範囲より2倍程度大きい範囲に対して調べるのを見つかるまで繰り返す。
  • 見つかったら、ここから回答を良くしていく。調査点を、今まで見つかった最小の答えの0.6倍~0.99倍程度でランダムで選び、そこから1e7の範囲で素数が存在するか調べる。これを繰り返す。

これで大体いつもの焼きなましっぽい形に変換できたので、ローカルで100個のテストに対して調べてみる。そうすると、この程度もので96%程度の問題に対して解答可能な範囲に解があることがわかったので、ミラーラビンはほとんどの範囲で使うことがないと判断。提出して90点台後半をげっと。ゎぁぃっ

回答の大半の分布が出たけど、1e12までで8割くらい(だったはず?)。1e13くらいまでで9割近く。思ったより大きい数字にはならなそう、ってのがこの段階で判明。

途中から考えたこと(submit7以降)

スタートダッシュはいつも通りうまく行ったんだけど、思ったよりすぐに抜かれちゃったので慌てて次のを考える。

ランキングを眺める

ランキングを眺めるのは結構有効。.00な人が大量にいる場合は凄く有効。ってことで、気づいたことを列挙してみる。

  • 56.00程度を取ってる人がいる

.00を取ってる人は、「最適解を出せる回答のみを提出していて、提出成功率が56%である」ということがわかるが、56%となると1e10くらいまでは出来てないといけない。これは自分の方法では無理。

  • 回答が異様に早い人がいる

普通探索するもんだと思うんだけど、提出してから点数がつくまでむちゃくちゃ早い人がいる。これって、「ランキングを眺める」とかそんなレベルでなく「ランキングに張り付く」レベルだからなかなか気づけないことではあるんだけど、一瞬で回答が出るってことはなんか変なことやってるんだろうなぁ、と推測可能。

(ちなみに、最大限で時間を使ってたら、100ケースの場合、.NET以外で5分、.NETで20分程度)

そこから適当に予想したこと

一瞬で回答するってことは、やっぱりあらかじめ回答を埋め込んでる、くらいしか考えられない。ということでどう埋め込んでるかを考える。

素数pに対して、p-a、p+bの範囲に対して云々、って感じでpを中心としての範囲である必要は一応あるものの、連続したa+b+1個の範囲において、素数がx以下、みたいな近似は一応可能。となると、array[x,a+b]みたいな2次元配列に埋め込める。a+bは250刻み、xは10刻みくらい?(これは後々範囲を縮めます。)

で、X=x/10, A=(a+b+249)/250くらいで考えると、十分な埋め込みデータが整っていれば、x,a,bの回答がarray[X,A]で即回答できます。これはまず1個大切なことだけど、ここで止まるとせっかく埋め込んだのが凄くもったいない。これを利用して求められるものは、「確実に回答が出る数値」だけではなく、「確実にこれ未満では回答が出ない数値」である、array[X+1,A-1]も求まります。自分よりxの使用量が多くて、範囲の狭いものでの最小回答なので、下から抑えることが可能。これで範囲を絞れば、ある程度大きい数字でも全探査が可能となる。可能じゃない程度に狭かったら上と同じ方法でおk

ということでせっせと1から計算して求めていく。スコアがきゅんきゅんあがって楽しいけど、2週間計算してもカバーできる範囲は85%程度。ここからが勝負?

 

たぶんこのあたりまで実装できてれば20位くらいです。疲れたので続きはまた今度!

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/chokudai/20100409
 |