Project Euler 295

プログラミング

久しぶりに難問のようです。
問題が公開されてから26時間経った現状で解答者が15人で、最も早い解答者でも3時間11分49秒かかっています。

効率的なアルゴリズムというものがよく分からない私に取っては最近のも全て同じくらい難しいのですけどね。
ということは、チャンス？と思ったのですが、結局解けませんでした。
N(10), N(100) は解けたのですが、結局パフォーマンスが問題になってしまいました。


なお、私の考えたコードでは計算時間は、 O(N^4) となっています。
すなわち、L(100000) は O(10^20) ...
ちょっち Ruby だと厳しいかなという感じ。
だけど、もっと厳しいのはメモリが足りなくなるということ。


いい方法が思い浮かばないので、とりあえず MySQL にデータを突っ込むようにして現在実行中です。
オンメモリではないので圧倒的に遅くなり、O(N^4) どころではなくなっていますね... orz


ちなみに、オンメモリのコードでの実行時間は以下のような感じです。

  • N(10): 0.0s
  • N(100): 1.34375s
  • N(1000): たぶん 2時間くらい (実行中) ->計算終わりました。5時間でした。

MySQLを使ったコードでは、N(100)で 13058s (3時間半くらい)。かかりすぎです。というか私のMySQL＋Ruby環境がなにか変な気もします。


と思ったら、気づけばバックグラウンドで実行していたMySQLが値を上げていました…。

dapters/abstract_adapter.rb:147:in `log': Mysql::Error: #22003Out of range value adjusted for column 'radius_square' at row 1: INSERT INTO `groups` (`radius_square`) VALUES(2147488281) (ActiveRecord::StatementInvalid)

値の範囲かぁ、これはコードで回避できるなぁ、、とは思いつつ、もう疲れたので終わりにします。どうせ時間は無限にかかってしまいますし。。


今回はランクインできるかもしれない、かもしれないと思ったのに…。まだまだ精進が足りません。

      • -

追記 (2010/6/8)
会社の同僚の助言を聞いて、O(N^2)の計算量で実装できそうなことが分かりました。
しかし、Rubyだとやはりメモリ的に厳しそうだということも分かりました。
まあ、２連続敗退ということですな。次はがんばろう。って次は深夜か。。厳しいな。