http://rosalind.info/problems/nwck/なかなか解釈することができなかった。 これで104問で95位に入った。 もうそんなに簡単に進められない。

http://rosalind.info/problems/list-view/やっとアルゴリズムパートが終わった。ソートの問題の後、ずっとグラフの問題を解いていた。 なぜバイオにグラフ理論が必要なのかというと、たぶんアセンブルに必要だからだ。アセンブルというのはシーケンスリード…

http://rosalind.info/problems/list-view/昨日までに64問解いた。 実は問題に色々なパートがあって、最初はBioinfomatics Strongholdというのを解いていたが、途中で気が付いて、Algorithmic Heightsというのを解いていた。これは純粋にアルゴリズムの問題…

http://rosalind.info/problems/list-view/Project Eulerが死亡してすぐにこのサイトを見かけた。前からあることは知っていたが。そして木曜からはじめてとりあえず10問解いた。ここはバイオインフォマティックス版のProject Eulerらしい。これを解いていく…

昨日の朝、落ちているのに気が付いた。しかし、いつも問題のページをいきなり見に行くので、メッセージは見なかった。メッセージを読んだのは夜遅くだった。http://projecteuler.net/index.htmデータベースが壊れているかもしれず、復旧の見通しは立っていな…

http://projecteuler.net/index.php?section=problems&id=47649着。 問題見て、これは考えてもムダな問題だと思った。昨日の夜少し検索して、今朝さらに検索した。日本戦の前に探したかったが見つからず、結局お昼になってしまった。そのあと食事に出かけて…

http://projecteuler.net/index.php?section=problems&id=474いろいろ手を尽くして4分11秒になったが、もう無理かな。

http://projecteuler.net/index.php?section=problems&id=474前から考えていた数論的手法を入れたら7分弱になった。高速化する前のやり方を変える段階でなかなかバグが取れなかった。

http://projecteuler.net/index.php?section=problems&id=47576着。3分。 日曜日、ナイーブな実装はすぐに思いついた。しかし、これでは答えは出ない。ほかにやりたいこともある。スルーする。 翌日、電車の中で考える。しかし何も出てこない。帰ってからナ…

http://projecteuler.net/index.php?section=problems&id=47475着。1時間半。 なかなか組んでいる時間が取れなかったが、なんとかした。 まだ速くする方法はある。数論を使う。1分にはならないと思うが。

http://projecteuler.net/index.php?section=problems&id=47362着。 昼からでかけてて、あまり時間が取れなかった。問題を読み間違えていてなんでこんなに小さい数になるんだと思っていたが、わかってしまうと逆に手抜きアルゴリズムでも解けてしまう。

http://projecteuler.net/index.php?section=problems&id=459前日書いた手法で100まで解が得られた。しかし、規則性がよくわからない。

http://projecteuler.net/index.php?section=problems&id=459こういう交互に手を出して最終的に行き詰ったら負け、というゲームはパターンが決まっている。状態sに対して関数f が存在して、 f (s) ∈ { 0, 1 } で、最終状態sendのとき、f (send) = 0、f (s) =…

http://projecteuler.net/index.php?section=problems&id=47218着。 最初、問題の図にあるようなナイーブな実装もなかなかできなかった。しかも、これだとN = 500さえ難しい。個数だけなら簡単だと思って組んでみた。しかし、これだとO(N^2)かかる。O(NlogN)…

http://projecteuler.net/index.php?section=problems&id=47113着。 この問題は、内接円の半径さえ求められるようになればいいはずだった。地道に計算してそれをなんとか求められた。そしてこれを高速化する。しかし、簡単なはずなのになかなか計算が合わな…

この問題で最も時間がかかるのは個々のRamvokの期待値を求めるところ。ここを工夫してPyPyで39秒かかるところを2.3秒にした。フォーラムに書いた。

http://projecteuler.net/index.php?section=problems&id=47068着。39秒。 最初ややこしくてなかなか英語がわからなかった。ただ、ちゃんと読んだらわかった。わかってしまえばなんということはない。ただの連立一次方程式を解くだけだ。しかし、スパースと…

http://projecteuler.net/index.php?section=problems&id=459この問題は唯一解けずに残っている問題である。 とりあえず一次元ならどうかと考えているのだがわからない。前のコードを書いたときはPyPyで21まで答えが出た。今回少し工夫してスピードアップし2…

http://projecteuler.net/index.php?section=problems&id=468いろいろ小手先の高速化を施したら、PyPyで7分が5分になった。 そして、最後に小手先といえば小手先だがフォーラムにも無い方法で高速化したら3分になった。 それをC++に翻訳したら18秒だった。 …

http://projecteuler.net/index.php?section=problems&id=46988着。 O(N)の方法はすぐに思いついた。しかし、これでは何年もかかる。 今朝考えていて近似を使うのかなと思って、ややこしい方法を思いついた。 しかし、こんなことをする必要はなかった。騙さ…

Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べ…

http://projecteuler.net/index.php?section=problems&id=46841着。7分。 土曜に風呂に入って考えたら簡単じゃないかと思った。しかし、日曜に組んでみると遅い。なぜ遅いのかわかった。O(N^2/logN)くらいになっているはず。しかし、C++でごり押しができるく…

http://projecteuler.net/index.php?section=problems&id=467103着。40分。 火曜の朝には解法に気づいていたが、コードを書く時間が無かった。 Pythonは多倍長整数が作れるからそのまま使えば速いと思って楽なコードを組んだが、最初はメモリエラー、必要な…

http://projecteuler.net/index.php?section=problems&id=46557着。3分。 月曜日にナイーブな実装をしてから、これはグラフの問題だと思った。しかし色々考えてもなかなか解に近づきそうにない。検索してもそれらしきものが出てこない。一方で、この巨大な空…

http://projecteuler.net/index.php?section=problems&id=46677着、4分。 先週の日曜日には解法を思いついていた。しかし平日はコーディングする時間が無い。昨日やっとコードを書いてあとは高速化するだけだと思っていた。今朝ある程度高速化したが、ある瞬…

http://projecteuler.net/index.php?section=problems&id=465今朝P(1)を数えて、131を確認して、そのあとP(2)に取り掛かったら気づいた。 コードを書いてみたら、P(50)が限界だった。

http://projecteuler.net/index.php?section=problems&id=464前から思いついていたデータ構造を昨日だいたい組んで、今日仕上げた。PyPyで25分になった。C++なら1分くらいかも。O(N^4/3logN)くらいのはず。

http://projecteuler.net/index.php?section=problems&id=46478着。40分。 日曜に思いついてPythonで組んでみたが、遅い。あれこれ考えつつも少しずつC++に書き直してみた。やっと答えが合うようになったと思ったら、少しメモリが足りない。工夫して工夫して…

世界は2乗でできている 自然にひそむ平方数の不思議 (ブルーバックス)作者: 小島寛之出版社/メーカー: 講談社発売日: 2013/08/20メディア: 新書この商品を含むブログ (13件) を見るこの本に、オイラーのバーゼル問題に対する執念が書かれていました。バーゼ…

http://projecteuler.net/index.php?section=problems&id=46351着。18ms。 問題を見て電車に乗って、ノートに向かって考えていた。しばらく手を動かしていたら方針が立った。よくあるパターンだ。しかし、分割の方法を少し間違えていた。それから、漸化式な…