Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-04-08

Marathon Match 58 @ TopCoder 16:16 Marathon Match 58 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Marathon Match 58 @ TopCoder - nodchipのTopCoder日記 Marathon Match 58 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

第一印象

  • 素数
  • ・・・
  • 無理。

とりあえずやってみる

  • Javaで書いてみる
  • ビット数決め打ちして素数生成してIsolatedかどうかを判定する
  • yesならビット数小さくする
  • noならビット数大きくする
  • Score:1.78
  • 先は長そうです・・・

問題文読み間違えていた

  • ついでにC++に移植してみる
  • ミラーラビン法を自分で実装してみる
  • と言ってもネット上のコードのC++移植
  • "a*b%c"の実装が面倒くさい
  • 多倍長乗算が必要らしい
  • Score:30.14
  • やっと戦えるところに来た

高速化してみようか

  • 素数判定が重いので小手先の高速化
  • Score:33.39
  • ううむ、上位陣は動やっているのだろう

あれ?これものすごく効率悪くね?

  • 素数を探すとき連続した10000個くらいを探すようにしてみた
  • Score:47.76
  • きた
  • 自分的にはもう目標達成てるのでいいかなぁ

浮動小数に手を出してみる

  • "a*b%c"は浮動小数を使うと高速化できるのではなかろうか?
  • 最初にa*b/cを計算して仮の商を計算する
  • a*bから引く
  • 以下正確な値が出るまで繰り返し
  • 出してみた
  • Score:47.25
  • 下がったorz

以上でタイムアップ

  • 途中で[x,2a]をキーとした素数を埋め込むことを考えたけど実装している時間がなかった
  • これを入れたらもう少し上がったのだろうか?

Handle Score Rank Last Submission Time Language Example Tests Submissions

nodchip 47.25 56 04.01.2010 01:48:35 C++ 9 5

nodchip 47.25 56 04.01.2010 01:48:35 C++ 9 5 16:16 nodchip 	47.25 	56 	04.01.2010 01:48:35 	C++ 	9 	5 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - nodchip 	47.25 	56 	04.01.2010 01:48:35 	C++ 	9 	5 - nodchipのTopCoder日記 nodchip 	47.25 	56 	04.01.2010 01:48:35 	C++ 	9 	5 - nodchipのTopCoder日記 のブックマークコメント

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