ザネリは列車を見送った ブログという名の備忘録

今回のは以前どこかで似た問題を解いていたものを流用して、
あまり解き方やアルゴリズムを考えずに解けてしまったが、こんなんでいいのやら…。

Problem 67. Maximum path sum II(最大経路の和 その2)

「Problem 18のずっと難しいバージョン」とのことなので、Problem 18をどうやって解いたか見てみたら、
覚えてなかったけどどうやら過去の自分は解法を自分で思いつかずググッていたらしい。
情けなや…と思いつつも、この「底辺から順に、隣り合う2つの数値のうち大きい方を1つ上の列の値に足す」操作を繰り返すことで
Problem 67も解けてしまった。実行時間も1秒かからず高速だ。

Problem 68. Magic 5-gon ring(Magic 5-gon ring)

今回の3問のうち、一から自力で考えて解いたのはこれだけになったな…。
euler61-2.hsなどと似たような形で、リスト内包表記で手続きっぽく書いてみた。
要領をつかむと、この書き方のほうが(僕にとっては)書きやすい場合もあるみたい。
ただ、3-gon ringくらいまでならまだいいけど、さすがにこれはちょっとゴチャゴチャし過ぎたか…。
うまくひとつの関数にしてfoldlなり何なりで呼び出すだけでOK、みたいにしたほうが良かったかもしれない。

select関数はProblem 43で使用したものを流用。
使い勝手が良さそうなのでZaneli.Eulerに入れてもいいかもしれない。

Problem 69. Totient maximum(トーティエント関数の最大値)

ん…オイラーのトーティエント関数…？
ちょうど並行してやっているL-99: Ninety-Nine Lisp Problemsでまさに同じ問題に出会ったばかりだ。
ということで、素因数分解を利用して解くことに。
これも公式を知らなければ互いに素かどうかをひとつひとつ愚直に試してパフォーマンスに悩まされる系の問題か。
n/φ(n)の最大値を出すために、いったんφ(n)とn/φ(n)のペアを作っているのは、
いつか教えてもらったシュワルツ変換の知識が活きた。
ところでφ(1)=1というのはL-99のP34(「Note the special case: phi(1) = 1.」)を参考にしたが、
その他にそう記載されている資料を見つけられなかった。
こうしないとゼロ除算が発生するためtotient 1 = 1としている。