プログラミング
http://projecteuler.net/index.php?section=problems&id=514ずっと考えていたら速くなる方法を昨日思いついた。O(N^4)だと思う。5.5秒になった。英語書かないと。
http://projecteuler.net/index.php?section=problems&id=51576着。 昨日、全然わからなかった。 今朝電車の中でp = 11で計算してみたが、何も思いつかなかった。 帰りに514を計算した後そのノートを見ていたら、ちょっと気づくところがあった。そこを計算し…
http://projecteuler.net/index.php?section=problems&id=51432着。2分半。 方針はちょっとややこしいが割と簡単に立った。それに沿って月曜にコードを書いた。しかし、E(2)すら合わない。E(1)は合った。 デバッグをするのだが、なかなか手計算と答え合わせ…
http://projecteuler.net/index.php?section=problems&id=51366着。 方針はすぐに立ち、コードを書くのがめんどうなだけだった。しかし、いざ完成してみると、メモリが足りない。いろいろ工夫してみたが、やっぱり足りない。 けれど、ごり押しすればメモリが…
http://projecteuler.net/index.php?section=problems&id=5121秒になった。 これは頻出テクニックを使う。パッと見、O(NlogN)っぽかったが、どうやるのか忘れていたので、帰りに考えていたら思いついた。 なぜこの問題に限ってごり押しが可能になっているの…
http://projecteuler.net/index.php?section=problems&id=51239着。80秒。 ごり押しするだけだったが、単純にコピペするだけだとメモリが4GBくらい必要だった。それで半分になるようにしたらギリギリメモリが足りないようだった。それでさらに半分になるが遅…
http://projecteuler.net/index.php?section=problems&id=51127着。 これは簡単だった。ただし、90秒ほどかかっている。速くする方法も思いついていない。
http://projecteuler.net/index.php?section=problems&id=490バグに苦しみながらも、とりあえず1乗の和なら速く出るようにした。しかし、3乗はなんともならない。フィボナッチ数列ならすぐになんとかなるんだけど、それよりも複雑なので難しい。
http://projecteuler.net/index.php?section=problems&id=50255着。3分。 F(10000, 10000)はつまらない理由で遅かった。 F(100, 10^12)が2分かかっている。これを何とかしたいが。F(10^12, 100)は非常に基本的。これを少し改良するとF(10000, 10000)が出る。…
http://projecteuler.net/index.php?section=problems&id=502ずっとうまく動かなかった幅が狭い時用のコードにつまらないバグを発見した。これでF(100,10^12)がようやく出た。2分だった。あとはなぜか遅いF(10000,10000)を何とかするだけだ。
http://projecteuler.net/index.php?section=problems&id=51081着。 簡単だが、いろいろ計算ミスをしていた。
http://projecteuler.net/index.php?section=problems&id=502もうちょっと考えて工夫したら、O(W^3)になるっぽい。
http://projecteuler.net/index.php?section=problems&id=502ちょっと工夫することによって、O(WH)になることに気が付いた。 しかし、Pythonで組んで動かしてみると、O(W^2H)っぽい。なにかPythonの罠があるのだろうか。全然わからない。
http://projecteuler.net/index.php?section=problems&id=502昨日から考え直している。前の方法はほぼ捨てて、なるべく違う方法をと考えた。 昨日の帰り電車降りる間際に高さが低い時の解法を思いついた。そして、今朝の電車の中でちゃんと整理して、帰って…
http://projecteuler.net/index.php?section=problems&id=5093問連続53着。狙ってもできない。 なにやら難しそうだったが、ジョギングしながら考えたら、実は簡単だということがわかって、S(10)が頭の中で計算できた。これ、3つじゃなくても簡単だ。この問題…
http://projecteuler.net/index.php?section=problems&id=50853着。全問と同じ。土曜になったのも。 日曜、全然わからず。 月曜、行き帰りに考えても何も思いつかず。仕方なく適当なキーワードで検索すると、やっと-1+i進数にする方法が分かった。ただ、解に…
http://projecteuler.net/index.php?section=problems&id=50753着。1時間40分。 水曜日にある問題に帰着することがわかって、その解法が木曜日の朝に完全にわかった。だが、なかなか時間が確保できず、結局土曜になってしまった。 なかなか素晴らしい解法だ…
http://projecteuler.net/index.php?section=problems&id=505昨日はじめてPythonで書いて、今日C++で書いてみた。PyPyに対して、3倍にしかならなかった。24時間以内かと思ったが、簡単にパラレルになるので4コアで計算してみたら8時間くらいかかった。
http://projecteuler.net/index.php?section=problems&id=503いろいろ工夫することによって高速化を図った。F(1012)まで計算したら、O(N1/2)っぽくなった。普通の解法ならO(N)である。 F(10^6) : 0.031sec F(10^7) : 0.090sec F(10^8) : 0.146sec F(10^9) : …
http://projecteuler.net/index.php?section=problems&id=50618着。 すぐに解法思いついたのに、デバッグにえらく時間がかかってしまった。
http://projecteuler.net/index.php?section=problems&id=503いろいろ計算して、とりあえず4倍速くした。
http://projecteuler.net/index.php?section=problems&id=50484着。 簡単な問題なのにデバッグに時間がかかってしまった。
http://projecteuler.net/index.php?section=problems&id=50382着。37ms。 木曜日までにだいたいわかって、金曜の朝、線形になることがわかった。しかし10^12だと勘違いしていたので、どうすればO(N)より速くなるか考えていた。しかし実際には10^6だったので…
http://projecteuler.net/index.php?section=problems&id=501144着。 なんとか土曜日中にできた。 単に素数の個数を数えるだけの問題なのに。
http://projecteuler.net/index.php?section=problems&id=500134着。 この問題は2のべき乗だから易しくなる。
http://projecteuler.net/index.php?section=problems&id=49865着。 すぐにわかったが、なかなかコード化できない。できてもなかなかバグが取れない。 夜遅くなったので寝て、翌日ちゃんと考えたらできた。 PyPyで76秒だったので、遅い部分を速くしたら0.7秒…
http://projecteuler.net/index.php?section=problems&id=49736着。 単純にハノイの塔を解くだけなのに時間がかかってしまった。
http://projecteuler.net/index.php?section=problems&id=49622着。 読み間違えていて苦労したが、なんとか式を出した。その時点ではよくわからなかったが、図書館に向かう途中で解法に気が付いた。 しかし、PyPyで解いてみると1時間以上かかりそうだ。C++で…
http://projecteuler.net/index.php?section=problems&id=49434着、40秒。 解法にやや疑問があるが。 いつもは時間が経つにつれ解けた人数が増えるペースが鈍っていくが、今回はそうでもない。すなわち、粘れば解ける問題。
http://projecteuler.net/index.php?section=problems&id=493111着。 問題を見た時にはもう106人も解けていた。 この手の問題は母関数かなあと思って考えてみたが、何も思いつかない。朝食を取りながら、素直に書いてもいいのかなと考えて、食べ終わってから…