http://projecteuler.net/index.php?section=problems&id=186 久々のproject euler. UnionFind,DisjointSetを知っていれば簡単． 問題は，どう関数型言語で実装するか，である(笑)． {-# LANGUAGE BangPatterns #-} import Control.Monad.ST (ST,runST) impo…

http://www.tatari-sakamoto.jp/skkime.jis.html から skkime1.5-winxp-bin-snap20081107.tar.gz を頂く． SKKI1_5U_WXP.INF を右クリックして，「インストール」を選択． あとは勝手に進んだ気がする． 辞書を http://openlab.ring.gr.jp/skk/wiki/wiki.cgi…

emacs 22.3 を windows にインストールした． MS-IMEは使わないので，これで良い． さしあたって， apel skk color-theme fixed-width-fontset redo を入れた． とりあえずの設定↓ ;;; -*- Mode: Emacs-Lisp ; coding: iso-2022-jp-unix -*-;;; ;;; Time-sta…

ちょっと使ってみた．良さそうだ． skkimeを入れてみよう． http://www.tatari-sakamoto.jp/skkime.jis.html http://mayokara.info/blog/archives/2008/02/24190204.php 1.5をいれてみる． SKKI1_5U_WXP.INF でインストール．右下のキーボードアイコンでMS I…

gs を使って windowsで gswin32c -q -sDEVICE=epswrite -sOutputFile=foo.eps -r9600 -dNOPAUSE -dBATCH -dSAFER -dEPSCrop foo.ps 意味はよく割らんが，epsファイルができるのでよしとする． pstoeditを使って pstoedit -f plot-svg foo.eps foo.svg これも…

http://projecteuler.net/index.php?section=problems&id=184 三角形を頂点ではなく、頂点と原点を結ぶ直線で考えた。 import Data.Function (on) import Data.Map (fromListWith,toList) choose :: [a] -> Int -> [[a]] choose _ 0 = [[]] choose [] _ = []…

http://projecteuler.net/index.php?section=problems&id=183logとって微分した。 del :: Integral a => a -> a -> a del p = until ((0/=).(`mod` p)) (`div` p) d ::Integral a => a -> a d n | (1==).del 5.del 2.div r' $ (gcd n r') = -n | otherwise =…

http://projecteuler.net/index.php?section=problems&id=182 p182 p q = sum [e | e <-[2..phi-1], gcd e phi == 1, gcd (e-1) (p-1) == 2, gcd (e-1) (q-1) == 2] where phi = (p-1)*(q-1) main = print $ p182 1009 3643 {-- g(e,p) = x^e=x (mod p) の解…

http://projecteuler.net/index.php?section=problems&id=181 import Data.Array (range) import Data.Array.IO (IOArray,newArray,readArray,writeArray) import Control.Monad (forM_) b = 60;w = 40 main = do g <- newArray ((0,0),(b,w)) 0 :: IO (IOAr…

http://projecteuler.net/index.php?section=problems&id=180 式変形する。はじめはnの範囲が有界でなくて、戸惑ったが、フェルマーの定理だった。 import Control.Monad (guard,liftM) import Data.Ratio (denominator,numerator,(%)) import Data.Set (fro…

http://projecteuler.net/index.php?section=problems&id=214 前にHaskellで挑戦して、どうも遅くて解けなかったが、 Problem 179を解いて、ふるいを使えば効率よくΦ関数が計算できることに気がついた。 手続き型のほうが書きやすそうなのでjavaで。 public …

http://projecteuler.net/index.php?section=problems&id=179 たいていの場合、素因数分解は重い。 エラトステネスのふるいとDPを組み合わせたようなアルゴリズム。 単純な繰り返しでかける。Cのコード。 #include <stdio.h> #define LIM 10000001 #define SQR 3163 i</stdio.h>…

http://projecteuler.net/index.php?section=problems&id=178 状態で考えると状態は今までの最小数字、最大数字、最後の数字で表現できる。 状態数は高々10^3。 import Data.Map (Map,unionWith,filterWithKey,mapKeysWith,fold,fromList) type State = (Int…

http://projecteuler.net/index.php?section=problems&id=177 対称性のチェックが大変。 素直な全探索なのでjavaにした。 賢い探索もあるみたいだが、やはり対称性の除外が面倒そう。 public class P177{ public static void main(String[] args){ int count…

http://projecteuler.net/index.php?section=problems&id=176 因数分解 から となる とすると だから (p,q)の組の数を考えればよい。（ただし、p,qは2の倍数) import Number p176 = (2*).product.zipWith (^) primes.reverse.map (`div` 2).factors.(+1).(2*)…

http://projecteuler.net/index.php?section=problems&id=175 前に似たような問題があった。 結論からいうとユークリッドの互除法のようなもの import Data.List step :: Integral a => (a,a) -> Maybe (a,(a,a)) step (p,q) | q == 0 = Nothing | p <= q = …

今日は一年分ぐらい英語を聞いて、一年分ぐらい話した気がするなー。 とりあえず、今後日本の外に出て行くなら、もう少し英語話せるようになったほうが良いね。 といことを痛感しました。

http://projecteuler.net/index.php?section=problems&id=174 まぁ、これもさっきと大して変わらない（と思う、もっと良い解法があるかも）。 import Data.List import Data.Array.IO n :: Integer n = 10^6 lamina :: Integer -> [Integer] lamina h = [l^2…

http://projecteuler.net/index.php?section=problems&id=173 回答者が多いだけあって簡単。 lamina :: Integer -> Integer lamina n = (sum.map (div n)) [4,8..4*m] - div (m*(m+1)) 2 where m = floor.sqrt.fromInteger.div n $ 4 p173 = lamina $ 10^6

http://projecteuler.net/index.php?section=problems&id=171 数字の出てくる順番は本質的ではない。 平方数を1^2,2^2,3^2,..9^2を使って分割。 その分割からできる数字の和を考える（permutations）。 総和をとる。 digit :: Int digit = 20 partitionToSqu…

http://projecteuler.net/index.php?section=problems&id=172 流れは前問と似ている。 まず、分割して、その出現回数を数え、和をとる。 久々に一瞬で走る。 import Data.List divid :: Int -> Int -> Int -> [[Int]] divid 0 _ k = [replicate k 0] divid x…

http://projecteuler.net/index.php?section=problems&id=170 忙しいといいつつも。 合間にやってるだけだよ。と言い訳。 最大を探すので、9876543210から逆辞書式順に探索。 最初の数は3の倍数で50未満だと分かる。（10桁制約） 多分、解は98????????の形。…

なんだか、忙しいです。

http://projecteuler.net/index.php?section=problems&id=169 2の累乗が出てきたら、2進数で考えたくなるのが人情。 少し観察すると、2が伝播していく、感じ。つまり、最後が2か、そうでないかで状況が変わる。 でいろいろやった結果、最終的に次のように考…

http://projecteuler.net/index.php?section=problems&id=168 先頭の数字と約数を決めると次々と後の数字が分かっていく。 これもまた、循環を利用。 import Data.List expand d hd = (div hd d:).unfoldr f.snd.g $ hd where f x | x == hd = Nothing | oth…

http://projecteuler.net/index.php?section=problems&id=167 偶数項が２つしかあらわれない、という事実を利用。 循環を考える。 メモリが足りなくなったので、STを利用。 しかし、まぁ、コードがきれいじゃないですね。 しかも、結局 $ ./p167.exe Stack s…

もう1月も5日である。正月僕はいったい何をしていたんだ？

今日バイクにＤＨバーを再装着した。 バーテープはがしたりが、結構面倒だった。 しかし、このバイクに次乗るのはいつだろうか？なんて思ってしまう。 運動不足だね、どう考えても。

http://projecteuler.net/index.php?section=problems&id=166魔方陣のような問題(同じ数字が何度出てもかまわない） brute force でもできるが、それでは面白くない。 とりあえず、数字をmod 2 して考えると自明解のほかに 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 …

http://projecteuler.net/index.php?section=problems&id=165 この問題は結構苦労した。 線分交差列挙問題 といったら平面走査法とおもい、実装しようと試みた（前から実装してみたいとは思っていた）が… 無理 例外処理が予想以上に大変だ。処理しなくてはい…