桃の天然水 このページをアンテナに追加

2016-03-12

[]Project Euler 459 Project Euler 459を含むブックマーク Project Euler 459のブックマークコメント

http://projecteuler.net/index.php?section=problems&id=459

139着。

2年以上前からずっとわからない問題だった。この1次元版はかなり考えていて、それでもまったくめどが立っていなかった。ただ、あの考え方をまだ取り入れていなかったので、そこに一縷の望みがあった。

Problem 495が解けそうになったので、先週の土曜日くらいからそのあたりを復習して、月曜日に少しコードを書いてみたらだいたいわかった。

二次元版も水曜にはO(N^3)ながらW(100)が出た。木曜日には最後の部分以外は頭の中ではわかって、金曜日には最後の部分のアルゴリズムも思いついた。土曜日の朝にささっとコードを組んだ。


パーフェクトは2年ぶり3度目。

現在17人で、日本人はほかに一人いるっぽい。


冬休みに入った時には未解決問題が6問あったが、時間がかかりながらも確実に解いていった。時間が経って考え直すと違う発想が出てくるようだ。

2016-03-08

[]Project Euler 495 Project Euler 495を含むブックマーク Project Euler 495のブックマークコメント

http://projecteuler.net/index.php?section=problems&id=482

90着。

正月明けくらいから考え始めた。

すぐに一つ方法を思いついたが、よく考えるとどうもうまくいかない。もう一つ思いついたが、これもうまくいかない。かわりばんこに考えていたら、どうも後者がうまくいく可能性があるように思えてきた。そこから少しずつ頭の中で高速化していった。これは必ず速くなるはずだというところを1週間かけて速くしたりした。ここで少しずつというのは数桁速くすることを意味する。

十分に実行可能な速度になったあとはメモリの問題になった。とにかく2GB以内に収めなければならないのだ。Pythonならその壁を突破できるが、PyPyに比べてPythonはメモリを食いすぎて論外。PyPyだとintのリストが1要素8Byteずつ食うので、だいたいいくつリストに入れられるかわかる。今思うと、NumPyPyを使えばメモリを節約できるのかもしれない。その限界があるため、同じ処理を何度も行わなければならなかった。その調整がうまくいかなくてメモリエラーになった。メモリの解放がうまくいかないのだ。以前から考えてはいたが、そうなったあとで、繰り返しする前にファイルに途中結果を書くようにして、またスクリプトを立ち上げるようにした。これで約30時間。かなり頑張ったと思う。

残りあと1問。

2016-03-03

[]Project Euler 482 Project Euler 482を含むブックマーク Project Euler 482のブックマークコメント

http://projecteuler.net/index.php?section=problems&id=482

129着。

日曜日に考え始めた。

この手の幾何学の問題は、どう式に落とし込むのかが問題だ。最初に考えた方法は、あまりうまくいかなそうだったが、2つ目に考えた方法はなんとかなりそうな感じだった。以前のノートを見てみたら、かなり複雑な式になっていて、これについてかなり考えていて、1週間以上経ってもかなり計算をしていたが、うまくいかなかったようだ。

とりあえず2番目の方法で考えてみたら、最初はメモリが足りなかったが、少し工夫したらメモリも問題なくなって、ナイーブなコードで10分になった。

残りあと2問。