Hatena::Grouptopcoder

chokudaiの日記

2010-04-14

MarathonMatch58 参加記その2

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

さて、ここから埋め込み対決です

埋め込みデータをどう使うか

他のデータを再利用

2次元データで上下が抑えられたからといって、それで満足してちゃもったいない!ということで、存在するデータは全て使います!

上下がわかったので、その範囲に入っている、埋め込みデータ全てに対して、狭い範囲で動作するかどうか確かめて見ると、大体途中で引っかかります。埋め込みデータ強い!まぁちょっと範囲が違っても、素数の密度が薄い場所をメモってくれてるんだから正しいと思う

このことから、時間内にランダムの焼きなまし的手法は完全に捨てても良い程度であることが確認できます。この当たりで正直「クソゲー」と思っちゃってたりもしました。

埋め込みデータ作成の高速化

広範囲に対するエラトステネスで一気に篩う

本番データでは、ある程度大きい数字になるとミラーラビンのほうが早くなる範囲が存在しますが、埋め込みデータは1億程度の範囲を一辺に調べたほうが効率が良いので、圧倒的にエラトステネスのが早いです。篩なめんな!

Cによる高速化

ここまで埋め込み勝負だとC#で作ったのはさすがに不利かなぁ、ということでCでデータ出力をさせてました。これは、「他の環境でも動かせること」も視野に入れて作ってたんだけど、結局動かせず

CUDAによる高速化

・・・調べてたけど出来なかったよ!w

データの格納方法

上記のように2次元配列の全体を結局使うんだったら、上から押さえたりしたから押さえたりができなくなるけれども、それでも1次元で重複なしでずらーっと並べたほうが、特徴点をもっとたくさん使えたのではないか?という疑問が発生

とりあえず、「今回のデータの格納方式から溢れるけれども、有効な特徴点」ってのを適当に拾い集めたら、微妙に点数がアップ 本当に微妙にだけど

上位の人はこれをやってそうだなーって感じはした

終了後考察

データの格納方法変更について

上位陣はやはり上記の格納方法を使っていた・・・んだけど、下にも書いたとおりやっぱり殆ど影響はなかったみたい。データの調査数の差が大きい

そもそも、自分のデータの調査数では、2次元で格納してて重複が大量発生することで発生するデメリットが感じられない程度に足りなかった、ってのもあるのかもしれない。ぶっちゃけ重複たくさんっていうのはそれだけ圧倒的に密度が薄い場所があるってことで、それならそんなに特徴点は多くない、って予想は大体正しかったみたい。

エラトステネスの範囲

KOTEHOK氏なんかはエラトステネスを自分よりかなり広範囲で最初にやってた模様。そもそもエラトステネスが自分のアトキンより早い!?みたいなのもあるんですが、それは言語差っぽいので保留w

狭い範囲においては自分の実験データだとミラーラビンのが早い、ってのが出てるんだけど、KOTEHOK氏の環境だとそうでもないのかなぁ、うーん?

データの調べた量

1位のKOTEHOK氏のデータ・2位のnamiajelszo氏のデータを自分のデータに流し込んでみると、主要な部分は1割残りませんでした><

ということで、検索できてる範囲がまるで違うみたい。(ついでに言えば、これを流し込めばほぼ同様のパフォーマンスが今の少し効率の悪いデータ格納方法でも十分に出せることも確認)

ということで埋め込み速度・スペック差が大きかったのかなぁ、っていうのが正直な感想です。くそげー!ばか!っていっちゃだめですか!

検索順序

小さいところでだいぶ落としてたみたいで、これは単純に小さい数字から試した数が足りなかったみたい。(6日くらいやったけど!)

もうちょっとそっちを重視するべきだった?他の人のソース見ると完全にそろってるところで、自分はそこまで調べてないよ!って奴が多いから、そうとしか考えられない

まとめ

8位以内は綺麗に埋め込みゲーだったんじゃないかなぁ、と思います。それより下の人は、埋め込む十分な時間がなかったか、何か足りなかったか、ってイメージです。(30位までのソースコードは一応目を通しましたが、見落とし大量にあると思います><)

それ以上は・・・スペック差じゃないのこれ!ばか!って言いたいけど、並列化とかが出来てない時点で自分の手数の足りなさが響いたのかも?埋め込みゲーは初めてだったから、これだけ点数が取れればむしろ十分かもしれない

Result

6位/375 Rating 2392 -> 2444

まぁこんなもんかなぁ、と思います。最終で2つ順位落ちちゃったけど

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位くらいです。疲れたので続きはまた今度!