Problem 256 を 紹介する - 落書き、時々落学 Problem 256 - Project Euler面白そう！ でも僕は ２５３問目 が解けず、止まったままです。皆さん代わりに解いてください。

1年以上かかって、ようやく、252問完答。 最後に残った問題は、Problem 198、Problem 241、Problem 252 でした。どれも手強かった。 Problem 198：やっぱり最難問題。Stern–Brocot tree を使おうと思ったけど、速い実装が書けなかったり、微妙な勘違いがあっ…

ようやく残り１０問に。 全問完答もできるんじゃないかという気がしてきた。 もう１年以上やってるもんな。 解くのに時間のかかった問題を並べてみると Problem 156 ： ただの分割統治法 Problem 186 ： ただのグリーディーアルゴリズム Problem 201 ： ただ…

http://projecteuler.net/index.php?section=problems&id=113 各桁の数字が昇順または降順に並ぶ数が10100未満でいくつあるか求める。 重複順列です。 main = print $ euler113 100 euler113 :: Integer -> Integer euler113 n = sum $ map nonBouncy [1..n]…

http://projecteuler.net/index.php?section=problems&id=112 すべての数字が昇順または降順に並んでいる数を考える。2 桁以下の数はすべてそうだが、桁が増えるとその割合は減っていく。そのような数の割合がちょうど 1% になるのはいくつのときか求める。 …

http://projecteuler.net/index.php?section=problems&id=111 1 を 3 つ含むような 4 桁の素数は以下のように 9 個ある。 1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111 n 桁の素数で、数字 d が最も多く含まれるような数の和を S(n, d) とおくとき…

http://projecteuler.net/index.php?section=problems&id=109 ダーツで、100 未満の得点でチェックアウトできる場合の数を求める。3 投以下で、最後は Double で終わらないといけない。1 投目と 2 投目は入れ替わっても同じとみなす。 1 投目と 2 投目が同じ…

１０８問目と同じ。

1/x + 1/y = 1/n を満たす x, y の組を考える。n = 4 のとき、解は (x, y) = (5, 20), (6, 12), (8, 8) の 3 組であるが、解の個数が初めて 1,000 を超えるのは n がいくつのときか。 ずいぶん前に解いたので、自分で書いたコードが読めなくなっていて、改め…

「最小全域木」を求める問題、だそうです。グラフ問題に疎い自分は超俺流アルゴリズムで実装したため、UPする気にならず、放ったらかしてました。 jeneshiccさんの方法が簡単そうなのだけど、fglパッケージを入れていないので、まずは自分で書くことに。 ど…

１９０問解いて、残り約３０問。 年内に２００問解きたかったけど、解けない問題がこれ以上増えないようにするので精一杯。 １週間、計算機を回し続けた問題とかあったり、自分の限界を嫌というほど思い知ってます。 でも、楽しい。

http://projecteuler.net/index.php?section=problems&id=104 最初の 9 桁にも最後の 9 桁にも 1 から 9 の数字が 1 回ずつ現れるようなフィボナッチ数で、最小のものを求める。 最初の 9 桁と最後の 9 桁だけ抜き出して計算しています。ただし最初の 9 桁を…

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は原点を中心に反時計回り／時計回りに並んでいることになるので、原点を含むと分…

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

ちょうど１００問になったし、夏休みも兼ねて、これからどうするか考えていたのですが、そもそも Project Euler 以外にネタが何も無いことに気づきました。正直どうかと思う。 という訳で、ぼちぼち再開します。

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 が等価だということが分かりました…

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 与えられたローマ数字を最小限の数字で表現するとき、どれだけの数字が節約できるか求める。 最初は与えられたローマ数字をいったん自然数に変換してから再度ローマ数字に戻していたのですが、ロ…