Project Euler 挑戦記念に各問題に一言ずつ感想（ヒント）を書いていこうと思います。
Ruby で計算機代数システム Abst を作りながら挑戦しています。
84
Rationalでは係数増加の影響で計算に時間がかかったので、浮動小数で計算しました。
計算を何回かループさせたところ、確率がある程度収束したので答えが出ました。
88
まず、4～13000ぐらいまでの N について、それぞれが product-sum となる k をすべて求め、その結果を元に答えを出しました。N が product-sum となる k を求める計算は N-1 以下の結果を使うことで高速に行えました。
90
最初、問題文を正確に読み取れず苦労しました。{1, 2, 3, 4, 5, 6}と{1, 2, 3, 4, 5, 9}は別々にカウントするんですね。問題さえ理解できれば、あとは総当たりで解けました。
94
"almost equilateral triangle" を半分にした直角三角形について、条件を満たすかもしれない原始ピタゴラス数をすべて求め、その結果を元に答えを出しました。
98
まず "square anagram word pair" になり得るペアを探したところ、40ぐらいしかりませんでした。
そのためそれらのペアについて、split(//) や join や Hash を使い正攻法で調べたところ、解けました。
101
連立方程式を何回か解き、ちょっと計算をすることで答えが出ました。
103
n=6 の場合の optimum set に対し "rule" を適応したら答えが出ました。
105
106問目の問題を参考にspecial sum setの判定法を考え、解きました。
106
数え漏れに注意が必要です。n=8の場合は231個の部分集合のペアをテストする必要があります。
107
コーディングに少し手古摺りましたが、その分楽しめました。とにかくリング状になっているところをなくすことで答えが得られました。
109
きちんと数えるだけで良く、それほど難しくありませんでした。
111
各dに対し、M(10, d) を大きい方から仮定して総当たりで調べていきました。プログラムを組むのは少し面倒でしたが、計算は一瞬でした。
118
総当たりで解けました。計算には10秒ぐらいかかりました。
121
Rationalで単純に計算し、答えを出しました。それほど難しくありません。
122
加法鎖(addition chain)のtreeを作成し、m(k)を調べました。
126
まず、cuboid W×D×H(幅,奥行,高さ) が与えられたとき、それを i 回目に包むために必要なブロック数を考えました。 これは w, d, h, i を変数とするあまり複雑ではない多項式として得られました。 後はそれを使って答えを求めました。
127
計算時間短縮のため、必要なradは予めすべて計算しておきました。cに対するループを回して解を求めようとしましたが、時間がかかりすぎたので以下の改良を加えました。まず、一つ目の条件は各a,b,cに対しgcdを一回計算するだけで確かめられます。条件2, 3と条件4の必要条件を満たすようにうまくループを回しました。必要条件rad(ac)<cを満たすようにループを回すことで大幅に高速化できました。計算には15秒ぐらいかかりました。
128
PD(n) = 3 になる可能性があるのは六角形の頂点の6方向だけかと思いきや、さらに絞れることがわかりました。 その限られた方向にある数を調べることで答えが出ました。 （12時の方向の数は各周ごとに2つ調べる必要があります。）
129
130問目と同様
130
132問目と同じアイディアを使って解けました。
131
数学的に考察したところ、\(n\) が立法数であることが必要条件とわかりました。
さらに考察すると、\(p\) が立法数の差で表されていなければならないことが分かりました。
後者の条件を満たす素数 \(p\) の数を数えるのは簡単でした。
132
この問題は面白かったです。素因数分解を試みるのは無謀ですね。数学的に考察したところ、突破口が見つかりました。
133
この問題も面白かったです。問題129で定義されているA(n)をどれだけ効率的に求められるかと、割り切れる\(R(10^n)\)の有無をどのように判定するかがポイントです。群の元の位数を求めるアルゴリズムを使ってA(n)を求めるようにしたところ、約1秒で答えが出ました。
134
数学的に考察し、\(\text{mod }p_2\) での逆元を求める問題に帰着して解きました。
135
\(x^2 - y^2 - z^2 = n\) となる \(x, y, z\) が存在するための必要条件を考察し、\(n\) に対するループを効率化して解きました。計算には30秒ぐらいかかりました。
136
\(x^2 - y^2 - z^2 = n\) が解を一つだけ持つ条件を考察したところ、n の素因数分解に関する条件が見つかりました。エラトステネスの篩で50,000,000まで素数判定しておき、その条件を判定することで解けました。計算には20秒ぐらいかかりました。
137
フィボナッチ数列の性質を利用して \( A_F(x) \) を有限の式で表し、2次方程式の解の公式を用いることで解けました。
138
原始ピタゴラス数を求める式をうまく利用して総当たりを行った場合、45秒ぐらいで答えが出ました。Bhaskara Brounckerのアルゴリズムと、すべての解を求める漸化式を用いた場合には、一瞬で答えがでます。
139
原始ピタゴラス数を列挙し、単純な四則演算を行うことで解けました。
140
137問目とまったく同じ方針で解けました。
142
最初 \(x, y, z\) に対する総当たりを試みましたが、計算量的に解けそうにありませんでした。
そのため、数学的に考察し、\(a^2 + b^2 + c^2 = d^2\) となる \(a, b, c, d\) を探す問題に帰着し、原始ピタゴラス数のリストを使い解きました。
143
数学的に考察し、総当たりで解きました。 計算には3時間ぐらいかかりました。 原始ピタゴラス数を効率的に求める方法を応用してディオファントス方程式の解を求めることで、もっとずっと効率的に解けます。
144
Math.tan や Math.atan を使って float 型で素直に計算したら解けました。
146
数学的に考察し、確認する必要のあるnを出来るだけ絞り込んでから、それらについて総当たりで条件を満たすか調べました。\(\mathbb{Z}/p\mathbb{Z}\)における平方根を求めるアルゴリズムを使って予め必要条件を調べておき、素数判定はmiller-rabinを使って高速化しました。計算には2分ぐらいかかりました。
147
問題は単純ですが、プログラミングはなかなか面倒でした。 斜め方向は再帰を使ったシンプルなアルゴリズムを考えました。
148
mod 7 でパスカルの三角形を考察したところ、綺麗な構造が見つかりました。 その構造を利用して計算することで答えが出ました。 なかなか面白い問題です。
149
縦・横・斜に隣り合ったマスの和の最大値を求める問題です。 必ずしも各列の全てのマスの和である必要はなく、如何に最大となるように連続するマスの和を取り出すかがポイントです。
150
sub-triangle の高さと位置に関して総当たりで合計を求めることで答えが出ました。 そこまでに求められている結果を利用することで効率的に合計を求めることが出来ました。 計算には90秒ぐらいかかりました。
151
batch の進行に伴う全ての場合とその確率を計算することで答えが出ました。
152
分母を払って整数のナップサック問題として解きました。 一部の荷物は使用しないと判断できたのであらかじめ計算対象から除外しました。 また、一つ一つの荷物が大きいためアルゴリズムを工夫しましたが、原因不明のメモリ不足で苦労しました。計算には2分ぐらいかかりました。
162
カウント対象の補集合の要素を数えました。最後に全体から引き、結果を16進数に直しました。
164
再帰的な関数を作り、キャッシュしながら計算しました。
169
\(f(2^e) = e + 1\)であることを利用し、再帰的な関数を作って計算しました。
172
0の扱いに注意し、再帰的な関数を作って効率的に数えました。
174
エラトステネスの篩のように先に篩処理を行い、最後に集計しました。
182
この問題はなかなか難しく、数学的にもプログラム的にも面白かったです。最初に\((\mathbb{Z}/p\mathbb{Z})^\times\)と\((\mathbb{Z}/q\mathbb{Z})^\times\)の元の位数を調べ上げ、その中から必要なものだけを選らんで篩処理を行い、その結果などを元に答えを計算しました。
183
\(f(N, k) = k \log(\frac{N}{k})\) のグラフを作成してみたところ、\(N\)の値によらず同じような形でした。その性質をもとに、\(N\)ごとに\(f(N, k)\)が最大となる\(k\)のあたりをつけてから正確な\(k\)を求めました。
\(M(N)\)が循環小数になるか、即ち \(\frac{N}{k}\)が循環小数になるかどうかは、分母の因子の2と5に注目して判別しました。
188
\((\mathbb{Z}/m\mathbb{Z})^\times\)における1777の位数を考えて解きました。面白かったです。
190
微分して極大点を求める計算を連立方程式に帰着することで、綺麗に解けました。
193
任意の自然数は平方数とsquarefreeな数の積に分解できることを利用し、再帰的な関数を作って答えを求めました。この方法では、計算に10分ぐらいかかりました。
197
実際に計算してみるとすぐに値が収束し、簡単に答えが出ました。
200
2 と 5 以外の素数は下一桁が 1, 3, 7, 9 のどれかです。 そのことに注目し、調べる sqube を限定して計算したところ、答えが出ました。
211
力技で、すべてのnについて\(\sigma_2(n)\)がsquareか調べ、答えを出しました。計算には40分ぐらいかかりました。
215
再帰的な関数を作り、引数ごとに結果をキャッシュして計算することで答えが出ました。計算には5秒ぐらいかかりました。
225
証明はわかりませんでしたが、2万項目ぐらいまで試し割りした結果を入力したところ、正解してしまいました。
235
s(5000)を計算しやすい形に変形し、ある程度回答の範囲を絞り込んだ後に二分探索法で答えを出しました。倍精度浮動小数点数の有効桁数は15桁ぐらいなので、float型の計算で問題ありません。
250
最初に集合の元をmod 250でグループ分けしておき、それを元にうまく数えました。計算には約15秒掛かりました。
271
2, 5, 11 など一部の素数は \(x^2 + x + 1\) を割り切らない。したがって、そういった素数 \(p\) が \(x^3 - 1\) を割り切るには \(p \mid x - 1\) でなければならない。これを利用し、調べる必要のある \(x\) を絞り込んだ上で、\(x^3 \equiv 1 \mod n\) であるかを確認しました。計算には6分ぐらいかかりました。
277
合同式を導き、拡張互除法などを使って解きました。合同式を解き条件を満たす\(a_1\)を求めるところではだいぶ混乱しましたが、どうにか解けました。
297
再帰的な関数を作り、制限値未満で最大のフィボナッチ数を使う場合と使わない場合とで場合分けして計算していきました。
315
問題文が長めで条件がいろいろあり、どちらかというとそれらを把握することに手こずりました。問題を正しく把握できてしまえば、あまり難しくありません。計算には17秒ぐらいかかりました。
317
シンプルで面白い問題です。円形にスライスしてそれぞれの体積を求めました。スライス数をある程度増やすと小数点以下4桁まで求まります。各スライスの半径が最大になる初期飛散角度は、独自に考えた4分探索法で調べました。
323
n-bit の場合に m 回目で \(2^n - 1\) になる確率を求める再帰的なメソッドを作り、それを作って答えを求めました。計算には3秒ぐらいかかりました。
345
単純な総当たりでは15!通り試す必要があり、これはなかなか大変です。しかし、これらの中には重複する計算が多数あります。重複を減らし効率的に総当たりを行うことにより、約1秒で答えが出ました。
346
3以上の整数nはn-1進数では11と表されます。したがって、各整数について長さ3以上のrepunitで表せるかどうかを判定しました。計算には約7秒かかりました。
347
MM(p, q, N) を \(p^e * q^f\) \((0 <= e, f)\) という形式で表せる N 以下の最大の整数とし、このメソッドを用いて M(p, q, N) と S(p, q, N) を作成しました。計算には5秒ぐらいかかりました。
364
「それ以上誰とも隣り合わずに座れる席がない」という状態を中間状態として利用しました。
即ち、その状態の前後のパターン数を別々にカウントして計算しました。
ただ、それだけでは処理速度が遅すぎたため、以下の改良も行いました。
modulo での階乗はあらかじめ必要な分を計算しておく。modulo での combination は階乗と拡張互除法を使うことで高速化。
365
あらかじめ \(1000 \lt p \lt 5000\) の範囲の素数 \(p\) に対して \(\text{M}(10^{18}, 10^9, p)\) を計算しておき、中国の剰余定理を使って解きました。
modulo での階乗の計算はウィルソンの定理を使って高速化しました。
381
ウィルソンの定理を使い素直に計算したら解けました。
387
条件を満たす可能性がある値だけをチェックしていくことで比較的簡単に求まりました。
389
全ての I の確率を調べ、その結果をもとに期待値および分散を求めました。計算には12分ぐらいかかりました。
[amazon asin="4048687158" /] [amazon asin="4894712857" /]