Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1136-4c91021c
この記事にトラックバックする(FC2ブログユーザー)

Marathon Match 58 - IsolatedPrimes (参加記録) (この記事を編集する[管理者用])

2010年03月25日02時から,2週間.

Source

Problem Statement
standings

問題概要

正整数xとaとbが入力で,以下の2条件を満たす素数pのうち,できるだけ小さいものを求める問題.
 p-aは2以上
 区間[p-a, p+b]の中に,素数はx個以下しかない
xは1以上500以下の自然数からランダムに選ばれ,その後,aとbは4x以上25x以下の自然数の中からそれぞれランダムに選ばれる.
得点は,各テストケースに対して,
 正しい答えが見つけられなければ0点
 そうでなければ 全参加者の中で最良の答え / 自分の答え 点
が得点になる.
実行時間制限は,テストケースあたり20秒,メモリ制限は1GB,ソースコードの制限は100KB以下.

自分の解法

m=1..500, n=4..25として x=m, a=b=nm の場合のできるだけ良い解をローカルで実行させて求めておいて,埋め込む.
m=x-10..x, n=4..25の周辺数字が素数かどうかをエラトステネスの篩で求めて,その周辺で解を探す.
後は,実行時間が18.5秒ぐらいになるまで,今見つけている解以下の数字をランダムに選んで,その周辺で解を探す.
エラトステネスの篩は,ビットで管理してて10^9ぐらいまでなら数十秒で求まるが,TCでのタイムリミット等を考えて,sqrt(埋込みデータから分かる自明解)と3*10^8の小さい方までの素数を生成した.

自分の提出コード: txt
埋込みデータ(各行m,n,答えの順番): txt

最後のExample submissionの結果

Example scores:
0) 23.0
1) 2.6246401E7
2) 2.964270028523E12
3) 913457.0
4) 1.1765599E7
5) 2.5656597746621E13
6) 1.0707335893E10
7) 5.75058381179363E14
8) 1.653104521E9
9) 4.0895759034007149E17
参加記録

Marathonは嵌ると無尽蔵に時間が吸い取られていくので,参加見送ってたのだけど,SRM465出れなかった代わりに参加.
SRMのかわりなので3時間までにするぞ,とか思ってたけど,やっぱり参加すると時間とられるなぁ….
3時間ぐらいで上位に取れるようになれば良いのだろうけどなぁ,今のままじゃ時間無尽蔵につぎ込んでも取れない.
終了直後の暫定順位で18位/376人で,目標だった上位20%には入れそうな感じ.
以下,時系列順のログ.

1日目 (2010年03月25日) ぐらい

出張(23日から28日まで)と重なってSRM 465に出なかったので,その代わりにSRM465と同じ時期から始まるこっちに参加してみようかなと考える.
でも,このときはまだ参加するかどうか迷ってる.
久しぶりの通常のMarathon Matchで,今回は問題が単純でVisualizerとかTesterすらなくて,いつもjava使い方いまいちわからん,怖い,とか言ってる自分には参加しやすい回.
取り敢えず,問題を読んだだけで,どうやるべきなのか妄想しながら眠る.

2日目 (2010年03月26日) ぐらい

ちょっと妄想してたが,結論としては,素数の分布とか理論的にわからんだろうし,基本的には無理ゲーで,埋め込みゲーではないの?
データを埋め込めるのは100KBまでだが,何を埋め込むのか.
 m=1..500, n=4..25として x=m, a=b=nm の場合のできるだけ良い解
を埋め込むのはどうか.
例えば,x=50, a=625, b=802とかの場合,埋め込まれてるx=50, a=850, b=850の解を返せばよい.
まぁ,試行錯誤だ.やってみよう.
そもそも,どうやってできるだけ良い解を探すんだ?
取り敢えず,ある区間の数に対して,Miller-Rabinで素数かどうか判定して,その区間内で制約を満たす素数pが存在するか判定するプログラムを書いた.
答えが小さいときは,どうにでもなるので,答えが大きいときのを埋め込みたい,とか考えてしまう.
取り敢えず,数字が大きいほど素数は疎になるので,ランダムで
 1~今見つかっている500 12500 12500の解
の数字を作って,その周辺だけ調べて,解を更新できるものは更新してみる.
….
そもそも500 12500 12500の解が1つも見つからない….
てか,Miller-Rabinが普通に遅いなぁ….(unsigned long long * unsigned long long) % unsigned long longとかあるしなぁ.
スペック(ノートPC)のせいでもあるのかなぁ….
….
20分後ぐらいに1個見つかった.
10分後ぐらいにもう1個見つかった.このときの解がたぶん2244609125265410803.
いやいや,これ駄目だ,この調子じゃ先が遠すぎる.
ていうか,やっぱり,大きいところは捨てて,小さいときに答えを完全に求めれるようにしたほうが良いよな.
Miller-Rabinのプログラムを小さいほうからまわしてみることにする.
10時間程度で計算終わるであろう範囲を指定して,動かして,ホテルを出る.
いってきます.


(小さいところから計算するんだったら,Miller-Rabinなんてしないで,普通に篩えば良いじゃんか,バカー)


ただいま.ホテルに帰る.
ノートPC電源落ちてる.
ホテルの部屋にカードさしてないと,コンセントの電気の供給も止まるのか!orz
5時間ぐらいは動いてた形跡がある…,これは….
あと5時間待つ暇があったら,エラトステネスの篩書いて,1から計算したほうが速いな.プログラム強制終了.
素数は適当に10^7ぐらいまで作っておくとして,10^14まで篩えるな.
で,サブミットするプログラムは,適当に最適解を埋め込んで,後は,nを落とした最適解の周辺を調べて,もっと良い解があるなら更新していく.
なぜなら,x=50, a=625, b=802の場合は,x=50, a=850, b=850の解を使ってたのだけど,幅625+802ぐらいの間に素数が50個以下しかないってことだから
 x=50, a=700, b=700
の埋め込んだ解の周辺調べたら,答えがありそうな気がする.
そんな感じで,取り敢えず,サブミットするプログラムも書こうか.
500 12500 12500の場合は,10^14以下の解とか見つかってないし,サブミットするプログラム中の条件判定はMiller-Rabinのやつで良いか.
埋め込もうとしたら,生の数字で書くと120KBだったら150KBだったか,埋め込めないこと発覚.
26進数でアルファベットの文字列で埋め込もう,90KBぐらい.OK.
取り敢えず,サーバー側での実行速度わかんないし,一度適当に20sで終わりそうな範囲を計算させてみるプログラムをExample submissionしてみる.
TLEの嵐!
うげー,ノートPCで13秒のケースが,TopCoder側のPCだと12.5秒とかだ…,TopCoderのマシンってこんなに遅かったっけ….
ノートPCで20秒以内に終わるのが目安で良いな.
答えも,ちゃんと正しいと判定されるかどうか不安なので,もう1回Example Submissionしよう.
と思ったら,間違えて,普通にFull Submissionボタン押しちゃった…,Noooorz
続けざまにExample Submission.
Exampleの結果は一応,全部正しい答えは返しているみたいだった.
Fullの結果は32.92点(テストケース100個で100点満点).あんまり埋め込んでないのでこんなもんだろう.
後は適当に,埋め込みようのデータ計算させつつ寝る.
しかし,chokudai先生がありえない点数取ってるんだよな.90点代後半.
この埋め込み戦術だと,答えが大きい場合にどうにもならないわけで,普通に埋め込みなどではなく計算しているのかな…?
もし,そうだとしたら,上位陣と下位陣にきっぱり分けられたりして,何か閃かないとボロ負けする予感.怖い.

3日目 (2010年03月27日) ぐらい

朝起きたら,98点台というわけのわからないスコアの人が登場.
chokudai先生が80点ぐらいに落ちてる.
やっぱり,答えが大きい場合は厳密に計算できてるわけじゃないんだ,なんかこの辺にありそうとかあたりをつけて計算できるのか…?
取り敢えず,1回間違えてサブミットしちゃったので,もう気にせず,埋め込みを増やしてサブミット.
31.03点→58.07点.おお,順調.
そして,サブミットしたら,1位の人やchokudai先生のスコアがちょっと減る.
やっぱり上位2人とは方針は違うような気がする.
よくわからない仮説を立ててみよう.
素数の密度が薄くなる地点ってどこだ?
エラトステネスで篩うことを考えたら素数^2の部分で段階的に薄くなってたりしそうな気もする.
プログラムで,今までの計算が終わった後,経過時間が19秒になるまで,ランダムに素数選んで,その素数の2乗付近を調べてみるとか言うのはどうだろう?
サンプルで2個ぐらい値が改善された…,うそん.埋め込み弱えぇorz
まぁ,埋め込みじゃ最適解見つけられない気もしてたが,こんなんでサンプル2つも値更新できるとは思わなかった….
後,それだったら速度も大切.
10^14まで篩えるので,エラトステネスの篩で良いんじゃないってことで,Miller-Rabin排除.
取り敢えず,最新の埋め込みデータに変更して,サブミットしてみる.
58.07点→67.31点.順調に伸びてる.もう潜水するとか今回は考えない方向で.
そろそろお出かけの時間.
10時間分程度で終了するぐらいのプログラムを動かして,ホテルを出る.今日はノートPCを持って,
5時間は電源持つので,どこかで適当にコンセント借りれば,ホテルに戻るまで大丈夫なはず…!




ホテルに帰ってくる.
そろそろ答えが見つからなくなってきた.答えが10^11ぐらいまでは探索完了.
ちょっとした高速化と,埋め込みデータ更新して,サブミットしてみる.
67.54点→72.04点.このsubmitでchokudai先生のスコアが80点を割った.
意外と見える場所にいる気がする.
でも,それは幻想で,この8点はたぶんとてつもなく大きい.
実際,もう何もアイデアなんて出てこない.1位は何をやっているのだ….
7位ぐらいの人は,点数が56.00とキリの良い数字.
これは,たぶん100個中56個のテストケースには厳密に答えを求めているんだろうなぁ…,で後はTLEとか.
これも凄いな.
何気に自分の点数もそうこうしてるうちに72.00とかなったけど,これは72個厳密に求めてるわけじゃない.


寝付けないので,ちょっとだけ色々試す.
これ,素数の2乗の近くが答えになりそうとか言ってたが,やっぱり全然そんなことないな.
普通に,素数の2乗の近くを調べるよりは,適当にランダムに選んで,その周辺を調べて方が改善することが多い….
サブミットしてみる.
72.00点→83.15点.あれ?
こんなに違うのか,素数の2乗は駄目だorz
埋め込みデータは1.3*10^11ぐらいまで計算完了.2~3時間計算して,新しい答えが見つからないとか起こり始めた.もう期待できない.

4日目 (2010年03月28日) ぐらい

やっぱりちょっと潜水してみよう.
埋め込みデータなくすとどのぐらいスコア下がるのかチェック.
結果待ちの途中に,サブミットしたコード常に0を返すことに気づく.
82.97点→0.00点.
まぁ,いいか.
今日はPCの電源つけたままは厳しいので,素直に埋込みデータを昼には計算しない.


京都に帰ってきた.色々疲れた.
これで,デスクPCが使える!
ちょっとだけ,デスクPCで埋込みデータ計算させてみる.
ノートPCの2倍ぐらい速い.
でも,明日から帰省するため,またノートPCの日々に戻る….

5日目 (2010年03月29日) ぐらい

デスクPCで計算してて,埋込みデータは3.8*10^11ぐらいまで計算.(朝10時JST)
取り敢えず,帰省してる時にMMやるつもりはあんまりないので,サブミットしてどれだけ落ちるか見てみようってことで普通にサブミットしておく.
0.00点→81.01点.暫定4位/165人ぐらいとかだけど,どれだけ潜っている人がいるのか.
まぁ,元々勝てる気はしてないし,目標は上位20%ぐらいに入れれば上出来かな.
じゃ,帰省する.

9日目 (2010年04月02日) ぐらい

もう上位がおかしい.ほぼ全てのケースで厳密に計算出来ているように見える.
京都に戻ってくると,埋込みデータが2.15*10^12ぐらいまで計算できてる.
取り敢えず,埋め込んで送るだけ送ってみる.
78.40点→83.12点 (暫定8位→暫定6位)
一応埋込みデータ更新は効くのか…,根本的に色々考えないと駄目だと思うけど何も思いつかないな.
埋込みデータが2.22*10^12ぐらいまで計算し終わった後に,このままでは最後まで計算できないので,計算範囲を毎回ランダムに選んで,良い解が見つかっから更新していく形に変える.
そして,ちょっとだけランダムで埋込みデータ更新したのをサブミットする.
83.12点→83.20点 (暫定6位→暫定6位)
微妙過ぎる.

10日目 (2010年04月03日) ぐらい

SRM前についでに埋込みデータだけ変えてサブミットしてみる.
83.10点→84.50点 (暫定9位→暫定8位)
正直点数変わるとは思ってなかったけど1点も上がった.

14日目 (2010年04月07日) ぐらい

ちょっと埋込みデータ変えたり,コードを整理したりした.
最後のサブミットは85.15点.
終了時の暫定順位は18位/376人.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1136-4c91021c
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。