2年近く放置していた当サイトを久し振りに覗いてみたら、なぜかコードが表示されない。何か仕様が変わったのだろうか？
Problem 68
1 - 10までの数を下の図の◯に入れて、各3つ組の和が等しくなるようにする。問題で与えられた方法により数の並びを表現した時に、16桁となる数の中で最大の数を求める。
problem 68
実はこの問題は飛ばしていたのである。6月ころに一回手を付けて、良い解法が思い浮かばなかったために保留としたまま、いつも気に留めていた。11月のある暇な夜、何気なくまたこの絵を見ていたら、ようやくコードが降りてきた。
ポイントは1から10の数字を、外側の5つと内側の5つのリストに分けて考えることである。例えば外側を[1,2,3,4,5], 内側を[6,7,8,9,10],とすると、5つの3つ組は
[1,2,3,4,5]
[6,7,8,9,10]
[7,8,9,10,6]
という3つのリストの縦並び（同じ位置の3つ組）で表現される。
この取り扱いさえ思いつけば、あとは素直に問題文をコードに落とし込むのみである。
計算効率は少し悪い。なぜならば絶対に答えになり得ないものも評価しているからだ。例えば、求める答えは16桁なので、10は必ず外側の5つに含まれる。内側に含まれた場合は17桁になってしまう。また、答えは7,8,9では始まらない。なぜならば外側の数字は5つあるので、必ず1つは7以下となるからである。 しかしその様な「明らかに答えでない」候補を上手く除外する方法を見出すことが出来なかったため、ロスを承知で全検索へ走った。それでも計算は1秒以内に完了する。
長かった☆
Problem 76
100を2つ以上の整数の和で表現する方法は何通りあるか
真正面から正直にぶつかっても解けそうだが、現実的には計算量の壁に阻まれて答えは出ない。一方、これは数学で言う「分割数」の問題だと見れば、分割数の漸化式を利用する解法もありそうだ。
しかしここは Problem 31 を思い出そう。両替問題である。
Problem 31 は2£を両替する方法は何通りあるかを問う問題で、使える硬貨は一般的なものが指定されていた。Problem 76 は100円を1円玉から99円玉という硬貨を用いて何通りに両替できるかという問題と同義である。従って、Problem 31 のコードを変更せずに丸々使える。
コードを使い回すのも大切☆
Problem 75
周の長さが12で、各辺の長さが全て整数の直角三角形は(3,4,5)だけである。
同様に24 -> (6,8,10), 30 -> (5,12,13) 等々、長さを与えれば3辺の長さが決まる。
中には120 -> (30,40,50), (20,48,52), (24,45,51) のように、ある周長に対して複数の直角三角形が存在する場合もある。
周長が1,500,000までの直角三角形のうち、３辺の長さが１通りしかないものはいくつあるか。
さて、解法の説明が難しい。全探索が上手くいかないことは容易に想像が付く。何かしらの方法で効率的に探索しなければならない。今回は割と事前の手計算が必要だった。
問題が円と直線が格子点で交わることの言い換えであると気付けば、なんとなく道が見えてくる。
をX,Yの連立方程式だと見て、与えられたLに対してX,Yがともに整数になるZが1つしかないような(L,Z)を探せば良いと分かる。それをナイーブに実装したのが以下である。
省ける計算がある。それは相似の三角形に対する評価である。例えば問題文に登場する周長120の直角三角形は3辺の組み合わせが複数ある。ということは、周長が120の倍数の直角三角形は、全て複数の組み合わせを持つことが調べなくても分かる。
なので題意を満たさない小さな三角形が見つかった時には、その相似形を評価対象から省くことで高速化を図った。しかし結論を言ってしまうと、計算時間が5分→4分程度の短縮にしかならなかった。
1番目の方法で計算時間が掛かる本質は、1つの周長Lに対して、ある範囲の斜辺の長さを全てチェックしていること、言い換えれば計算量がO(N2)であることにある。相似形の評価を省いたところで、基本的な評価方法は変わらず、計算量がO(N2)であることも変わりはないので、劇的な短縮にならないのはある意味当然なのかも知れない。
早くならない…★
Problem 74
145 → 1! + 4! + 5! = 1 + 24 + 120 = 145 である。
このように各桁の階乗の和を取る作業を繰り返すことで、一連の数列を得ることができる。例えば169なら 169 → 363601 → 1454 → 169 と長さ3のループ（4回目でもとに戻る）を得る。
完全なループにならない場合もある。例えば
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
長さ60の数列を生成する数は1から1,000,000まで中にいくつあるか。
ある範囲の数に何らかの処理を施した結果に対し、最大値や◯◯の性質を持つものが全部でいくつあるかを問うのはProject Eulerの常套である。大抵の場合は同じ計算が繰り返し出てくるため、連想リストを使って2度目以降は計算を省いて結果のみを参照する作戦も既に自分の中では常套手段になっている。
今回出てくる繰り返しは、同じ数字の並べ替えに対する数列の長さの計算である。問題にある長さ60を生成する最小の数は1479であるが（これは探せば見つかる）、1,4,7,9を並べ替えた数（例えば4791）も当然長さ60の数列を生成する。これは数列の作り方から明らかである。
単純に考えて、4桁の数に対して24回、5桁の数に対して120回は同じ計算が登場する見込みだ。実際は先頭がゼロになるケースとか、あるいは先の4791に対して4790のように1を0に置き換えられるケースとか（0! = 1! なので）、色々あるわけだが、とにかく同じ数字を使っている数、もっと言えば各桁の階乗の和が同じ数同士、は同じ数列を生成する。
ということで1つ覚えの連想リストを使ってみるのである。思惑通り計算スピードは格段に早くなる。（後で比較のためにナイーブな計算と比べると20〜30倍は計算時間が違う）
そんなわけでData.Mapを使って計算結果を記憶しながら、1,000,000までの数を走査していくことにしたが、実は今回はそれと別の目的でもData.Map.Mapを使っている。それはループの判定である。各桁の階乗の和をつないで数列を作っていくわけだが、その結果を単純なリストにすることもできる。その場合、1回和を計算する度に、出てきた答えがリストに含まれているかをelmを使って調べなければならない。その処理時間はリストの長さNに対してO(N)である。仮にリストでなく木を使えば、処理時間はO(logN)になる。リストの長さはまちまちだが、最大60ということが分かっているので、それくらいの探索はしなければならないのだろう。リストの長さが10でも4倍、60なら15倍、探索時間に差が出ることを考えると、ループの判定にも連想リスト使ってみようと思った。Haskellの連想リスト（Data.Map.Map)は二分木だからだ。
長々書いたが、決して美しい出来ではない。もっと良い方法はあるのかも知れない。ハッキリ言ってMapでゴリ押しするのはダサいような気もする。しかし早いからやめられない。もっと美しい方法があればいいが。
普通☆
Problem 73
分母が12,000以下の既約分数は1/3と1/2の間にいくつあるか。
いくつかの方法を試すが計算が終わらない。これは例によって「知らないと解けない」系ではないかと疑い周辺情報を調べた結果、"Farey sequence"という有名な数列に関する問題であることが判明。それだけでもやられた感があるが、このFarey sequenceが非常に興味深い。この数列の性質と問題の解法はむちゃくちゃ深い。超高速アルゴリズムもありそうだ。
今回はそこまで掘り下げる力がなかったので、隣り合う2数から次の数を求めるアルゴリズムをwikipediaから拝借してお茶を濁す（日本語版にはこのアルゴリズムは載っていない）。はっきり言って敗北感しかないのである。
それでも第2項が4000/11999になることは自力で計算した。
数学の深淵を見た…★★★
