http://projecteuler.net/index.php?section=problems&id=103 大きさ n の集合 A の要素の和を S(A) とおく。空でなく共通の要素を持たない２つの部分集合 B, C が、以下の性質を持つような集合を特別な集合と呼ぶ。 S(B) ≠ S(C); つまり、部分集合の和は等…

http://projecteuler.net/index.php?section=problems&id=105 １０３問目の関連問題。 大きさ n の集合 A の要素の和を S(A) とおく。空でなく共通の要素を持たない２つの部分集合 B, C が、以下の性質を持つような集合を特別な集合と呼ぶ。 S(B) ≠ S(C); つ…

http://projecteuler.net/index.php?section=problems&id=106 １０３問目の関連問題。 大きさ n の集合 A の要素の和を S(A) とおく。空でなく共通の要素を持たない２つの部分集合 B, C が、以下の性質を持つような集合を特別な集合と呼ぶ。 S(B) ≠ S(C); つ…

出席の連絡を忘れていた。帰ったらする。

http://projecteuler.net/index.php?section=problems&id=102 与えられた三角形の中で原点を含むものの数を求める。 ∠AOB, ∠BOC, ∠COA の外積を取って、全て正／全て負ならABCは原点を中心に反時計回り／時計回りに並んでいることになるので、原点を含むと分…

インストールしました。OS は RedHat Enterprise Linux ES 4 。 tarball を持ってきて、./configure, make, make install しただけ。 6.8.2 のときもそうだったのですが、Data.Map をインポートしたコードをコンパイルしようとすると、↓のエラーが出て、コン…

http://projecteuler.net/index.php?section=problems&id=101 一般項が n 次の多項式となる数列を、より低次の多項式で近似するとき、最初に不一致となる項を求め、その和を答える。 部分数列から次の項を推定して、その和を求めています。そのとき、階差数…

http://projecteuler.net/index.php?section=problems&id=100 青いディスク 15 枚、赤いディスク 6 枚、計 21 枚のディスクの中から 2 枚のディスクを無作為に取り出すとき、青いディスクを 2 枚取り出す確率は P(BB) = (15/21)(14/20) = 1/2 となる。 青い…

http://projecteuler.net/index.php?section=problems&id=99 与えられた底と指数の組の中で一番大きいものはどれか求める。 cut-sea さんがSコンビネータについて書いてるのを見ながら色々試してて、flip f g と f . g id が等価だということが分かりました…

勉強会の内容を受けて、以前に書いた１９問目のコードを書き直してみました。 算術演算は使わず、カレンダー情報を１次元のリストに格納しています。 西暦 0 年から始めて 1900 年まで読み飛ばすとか、けっこう無駄なことをしていますが、所詮 O(n) なので、…

CARE という単語の各文字を 1, 2, 9, 6 の各数字で置換すると 1296 = 362 という平方数になる。文字の順番を入れ替えた RACE という単語も 9216 = 962 で平方数になる。与えられた単語の中からこのような単語の組を全て見つけ出し、平方数の最大値を求める。…

メルセンヌ素数ではない素数 28433×27830457+1 の下十桁を求める。 main = print euler097 euler097 :: Integer euler097 = mod (28433 * 2 ^ 7830457 + 1) (10 ^ 10)

http://projecteuler.net/index.php?section=problems&id=96 数独の問題を解く。 データ構造として、値の入った二次元リストのままだと解きにくかったので、座標と値をセットで持つタプルを使いました。 アルゴリズムとしては、取り得る値の範囲が小さいマス…

http://projecteuler.net/index.php?section=problems&id=95 ある数に対して、約数の和を求めるという操作を繰り返すとき、無限ループとなる数がある。そのようなループのうち、どの要素も百万を超えない最長のものを求め、その最小の要素を求める。 これま…

http://projecteuler.net/index.php?section=problems&id=94 辺の長さも面積も整数となるような正三角形は存在しないが、5-5-6 のような似非正三角形であれば、面積は 12 で整数となる。 このように辺の長さが1つだけ（長さ 1 以内で）異なる似非正三角形の…

http://projecteuler.net/index.php?section=problems&id=92 ある数の各桁の数字を二乗して和をとるという操作を繰り返すとき、どのような数から始めても、1 または 89 を必ず含む無限ループとなる。一千万未満の数のうち、89 を含む無限ループに陥るものが…

http://projecteuler.net/index.php?section=problems&id=93 {1, 2, 3, 4} の各数字と四則演算子 (+, -, *, /) を組み合わせて自然数を構成するとき、全部で 36 の自然数を構成でき、そのうち 1 から 28 は連続している。任意の 4 つの数字を選ぶとき、連続…

http://projecteuler.net/index.php?section=problems&id=91 0≦x≦50, 0≦y≦50 の格子上に点 P, Q を置き、三角形 OPQ を考えるとき、△OPQ が直角三角形となるのは何通りあるか求める。 P, Q を適当に配置し、各頂点の内積を計算して直角三角形かどうかを判定…

http://projecteuler.net/index.php?section=problems&id=90 2 つのサイコロの各面に、0 から 9 のうち任意の数字を選んで振り、それらを並べて 2 桁の数を作るとき、100 未満の平方数が全て表現できるような数字の選び方は何通りあるか求める。ただし 6 と …

http://projecteuler.net/index.php?section=problems&id=89 与えられたローマ数字を最小限の数字で表現するとき、どれだけの数字が節約できるか求める。 最初は与えられたローマ数字をいったん自然数に変換してから再度ローマ数字に戻していたのですが、ロ…

たぶんすごく馬鹿なことを聞いてるんだと思うのですが…。 一つの引数が複数回登場するような関数ってポイントフリースタイルで書けるんでしょうか？ たとえば diff xs = zipWith (-) (tail xs) xs とかなんですが。 どなたかこっそりご教示いただけると嬉し…

http://projecteuler.net/index.php?section=problems&id=87 28 = 22 + 23 + 24 であり、素数の2乗、3乗、4乗の和として表すことができる。 このような数は五千万未満でいくつあるか求める。 色々な素数について2乗、3乗、4乗の和を求め、重複するものを除い…

http://projecteuler.net/index.php?section=problems&id=88 2以上の自然数 k に対して、N = a1 + a2 + ... + ak = a1 × a2 × ... × ak を満たす最小の数を考える。例えば k=3 のとき、6 = 1 + 2 + 3 = 1 × 2 × 3 が最小となる。2≦k≦12 に対してこのような数…

unfoldr の練習の続き。unfoldr で書かれているコードを、他の関数で書き換えてみる。 もとのコードはこれ。Tabulation法で両替問題を解くコードの一部です。 mkqs :: [Count] -> Coin -> [Count] mkqs ps c = unfoldr phi (ps, []) where phi (p:ps, qs) = …

http://projecteuler.net/index.php?section=problems&id=85 3 × 2 の長方形は 18 個の長方形を含んでいる。二百万に最も近い数の長方形を含む長方形の面積を求める。 a × b の長方形が含む長方形の個数は ab(a+1)(b+1)/4 となるので、(a, b) = (1, 2000) か…

http://projecteuler.net/index.php?section=problems&id=86 6 × 5 × 3 の部屋を隅から反対の隅まで壁伝いに移動するとき、最短距離は 10 で整数となる。m × m × m 以下の大きさの部屋について、最短距離が整数となる部屋の数を考えると、M=100 のとき 2060 …

勉強会で unfoldr を教わったので、unfoldr 厨になってみる。 どこに使えるかなと考えてみて、種からリストを生成してるんだから iterate と同じじゃん！と思って、２６問目を書き換えてみました。 もともとのコード。「ウサギとカメ」です。 cyclePart :: […

http://projecteuler.net/index.php?section=problems&id=84 モノポリーには 40 のマスがあるが、それぞれのマスで停まる確率を求め、TOP3を答える。 Project Euler では問題文が長いのは嫌われる傾向にあるみたいですが（５４問目とか）、この問題は色々な…

http://projecteuler.net/index.php?section=problems&id=82 80 × 80 の行列を左辺から右辺まで、右か上か下に移動しながら辿るとき、各点の値の合計の最小値を求める。 行列をタテヨコ変換して、後は最小値を求めていくだけです。 import Data.List main = …

http://projecteuler.net/index.php?section=problems&id=83 80 × 80 の行列を左上から右下まで、上下左右に移動しながら辿るとき、各点の値の合計の最小値を求める。 次に進むべき点が分からないので、これまで通った点の近傍を進むべき点の候補としてリス…