Project Euler

Problem 237

問題の解き方は分かったのだが解いていない. Z/10^{8}の計算と行列を組み合わせれば何とかなるみたい.

Problem 206

なんで今まで残しておいたんだろうか. 基本的には総当り. 1/50くらいのステップに出来るので刈り込んで20秒ちょい.

Problem 155

方針が間違っているので後で直さないといけないが, とりあえずハッシュの方が相当速いことが分かったのでメモ. a2の方が冗長なアルゴリズムだが, それでもa2の方が速い. n=18くらいまでは簡単にいける. (use gauche.collection) (define (a1 n) (define (f l…

Problem 104

ようやく解けた. 現段階だと10分掛かってるのでもっと短くしよう.

Problem 214

Problem70だかProblem72だかで使ったものを再利用して解いた. n=2〜4,000,000のphi(n)を求めるだけで60秒掛かっているのが難点か. もっと速くなる気もする.

Problem 203

なんで前回解けなかったのか分からない. 富豪的にgroup-collectionを活用しても, 0.072秒. Pen4からCore2Quadに変えた所為もありそうだが.

Problem 225

久し振りにProject Eulerを解く. 最近追加された中で一番楽そうだったものを選択. 某アルゴリズムを使わなくても13秒. 使うと3秒であった.

Problem 209

ようやく解けそうな気がする. 巡回の様子は考察出来たのであとは数え上げ. 適当に条件付けた後に, メモ化して計算して終了.

Problem 178

4/29以来か. DPで解けるということに気づいたのでプログラムするか.

<a href="http://projecteuler.net/index.php?section=problems&id=188">Problem 188</a>

タワー表記かよ. 実はあっさり解ける問題. (define (find a b n) (define (order a n) (let loop ((i 1) (c a)) (if (= c 1) i (loop (+ i 1) (remainder (* c a) n))))) (if (= b 1) (remainder a n) (let1 o (order a n) (expt-mod a (find a (- b 1) o) n…

Problem 135 Problem 136 x^2 − y^2 − z^2 = nについて正の項からなる等差数列(x,y,z)を解として考える. 135は10^6未満のnで解がぴったり10個になるものの数. 136は5*10^7未満のnで解が一意に定まるもの. 手を動かすとアレの解の構造を決定する問題になるの…

止まってる

暫く機能停止らしい. やっとx>y>z>0が等差数列でx^2-y^2-z^2=n (Prob 135, 136) が分かったというのに.

Problem 157は面白かった. アルゴリズムを改良するとまだまだ縮みそうではあるが本業の方をいい加減やらないといけないので改良は止めておく. gosh> ;(time (apply + (map (lambda (n) (length (solve n))) (iota 9 1)))) ; real 38.250 ; user 37.843 ; sys…

詰まり中

108と110. 1/x + 1/y = 1/n で, 0 < x <= yという整数解の個数に関する問題. 解の構造は分かった. ぱっと思いつく方法だと1分ルールに反するので, 逆を考えるべきなのだろう. そういう方針であれば110の方も何とかなるのかな. 多分.またRioさんに離された. …

127問. Repunit系は129だけ残ってしまった. 位数を求めるのは面倒臭いなぁ. PROB119はこっちの方向が良いんだな. num->digitsは各桁にばらす関数 (use srfi-42) (list-ref (sort (list-ec (: b 2 1000) (: e 1 50) (if (and (> (expt b e) 10) (= b (apply +…

総合大会中に多少解いてたらしい. ようやく122問. Problem 26 面倒臭がって残していただけ. Problem 93 0除算? +inf.0になるからGaucheだと大丈夫. Problem 164 数え上げ. 漸化式を立ててメモ化で終了.

112問. 数え上げに関する問題を解いた. 113, 114, 115とか.

やっとこさ98問100問. Problem 72 手元の計算結果では一番高速なものでgauche, Pen 4 3GHzで2.781s. Problem 79 手計算の方が速い. Problem 80 SICPで課題問題だったと思うんだが. 普通にdecimalクラスを作って例の方法で近似. 2乗根の場合は古くから使われ…

篩法のメモ

参考: d:id:odz:20080229:1204287954 Project Euler用のメモ 100万までの各数について真の約数の和を求めることを考える. C系だとこんな感じ. long[] a; a.length = 1000000; for (long i = 2; i < 1000000; i++){ for (j = 2; j * i < 1000000; j++){ a[j *…

84問. ポインタも分からぬままC++の練習としてProblem 23とProblem 70を解いた. ポインタを使うところが無かったのでまぁいいのか. 言語を変えると力技で解けるってのはどうかと思った. Problem 70はあと一歩でC++を使うことなく解けたらしい. Problem 89がW…

80問ヽ( ´ー`)ノ 最初の方の簡単な問題を解き忘れていたので解いた.

<a href="http://projecteuler.net/index.php?section=problems&id=182">Problem 182</a>

RSAでm^e mod n = mとなるmの個数を最小化するeの総和を求める問題. 暗号屋としては解かねばなるまい. 数論系の暗号は久しぶりなのでちょっと迷ったが, 一応解いた.

70問( ´ー`) 801-900に入った. 条件付き最短パス探索問題 (Problem 81とProblem 82) は面白いな. n次正方行列について, Problem 81は計算回数がO(n^2)のアルゴリズムか. Problem 82はO(n^3)のしか思い浮かばなくて80s位掛かる. もう少し練るべきか. 条件の…

Problem 69 騙された(;´Д`) 気付くまでに20分掛るのは暗号屋としてどうかと思う. 62問になったので上手くいけばTOP 1000入り.

60問ヽ( ´ー`)ノ もうちょっと頑張ればTOP 1000か. 動的計画法を知らなくても陸プログラマでも何とかなるものだ. Problem 169とか普通の再帰+メモ化で何とかしたしな. それで出来るように丁度良く問題が作ってあるんだねと納得.

ようやく51問. Problem 183はそこそこ簡単だった. 先に手を動かすのが大事なのか.

Problem 59は暗号文の解読なのだが鍵が3文字で暗号文が1201文字なので, 頻度解析を行えば手でも出来る気がしてきた. XORがちょい面倒っていうくらいか.

素数判定

2/9を終えたところ. nが341550071728321未満のときまでは素数判定がO(log^3 n)か. Miller-Rabinテストはやっぱり偉いんだなー. ところで本業の方をschemeで書くという暴挙はどうだろう. LLLとか実装すんの. 大変そう. ;Refs:http://www.ice.nuie.nagoya-u.ac…

<a href="http://projecteuler.net/">Project Euler</a>

やっとこさ30問. 全体で182問なので, 先は長いなぁ( ´ー`) CかC++かDの練習をする心算だったのに何故かgaucheで解いている.

<a href="http://projecteuler.net/">Project Euler</a>

解けるものからガシガシと. プログラムの練習がてら, 目標を70問としてやることにする. 100万までの素数表を作るのが面倒なので(define PRIMES (list ...))とxyzzyのscheme-modeからgaucheに喰わせようとしたら落ちた.