ここ数日久しぶりに Project Euler 解いてる気がする。せっかくなのでまだ解けてない問題を振り返ってみる。 241 Perfection Quotients: これは相当な時間をかけてる気がしますけど，いったいどうやればいいのか見当もつかないでいます。素因数は 1.4e9 ぐら…

昨日の続き。200 以降。 212 Combined volume of cuboids: これはそういうアルゴリズムがあるのだろうか。調べてみるといいかもしれない。 226 A scoop of blancmange: たぶん難しくないんだろうけどなぜか手が動かない問題。なぜだろう。 229 Four represen…

とりあえず 200 まで。 161 Triominoes: たぶん方針が見えてるのでやればできると思っている。 167 Investigating Ulam sequences: Google で検索かけたところいくつかの性質が知られているらしいのでそれを組み合わせればできそう。本当にできるかどうかは…

ずいぶん長い間解けないでいた問題をとりあえず解きました。forum を読んだ感じだと，これは素数判定をする問題だったようですね。素数判定をやらない解き方を紹介してみます。遅いです。あと細かい調整や最適化がいくつかありますけどたいして面白くないの…

一年半くらい分からないでいた Problem 216 が解けました。わあい。他の問題の forum でネタバレしただけですけど。

解きました。ひたすら計算するだけなのに二日かかりました。数値計算苦手。あと -0.01 0 を忘れてて incorrect をもらって，半時間ぐらい悩みました。

Problem 140 解けました。これ結構難しいと思うんですけど、なんでみんな解けてるんですか。検索したら解き方出てくるんでしょうか。

one minuts rule をどうやったらクリアできるのかよくわからないけど面白い効率化も思いつきそうになかったので brute-force したら30分ぐらいでできました。あんまりすっきりしない。もやもや。

頑張ったら 263 が解けて、ついでに正二十面体に昇格しました。ところで辺の長さを同じにとると正二十面体よりも正十二面体のほうがだいぶ大きくなるので、そういう基準で見るとむしろ降格した気分になったりならなかったり。

年末に出た 224 をようやく解きました。方針が見えて昼までに解けると思ったからやったのに、夕方までかかってしまいました。よくあることですが、これ三角形ほとんど関係ありませんね。ただの整数の問題。

正解者がかなり少ない問題でしたが、何とか解けました。土曜日から今日の夕方まで起きてる時間の半分はこれに費やしたような気がします。方針が立ってからそれを実現するまでがわりと大変で、おそらくこの方程式を解けばできるだろうと予想はついていても、…

一応正解は出しましたが、わりと brute-force なので改善したいところ。いくつか枝刈りできると思ったところがあるのに、実際に刈ってみると答えが変わります。もう一度落ち着いて、一から紙に書いて考えないとだめか。

110 前後で未解答のままになっていた比較的簡単そうなものをいくつか解きました。やり方はなんとなく思いついても、コードを書くのが面倒だなー、と思って放置していたものが多いのですが、書いてみればそんなに大変でもなかったりします。いきなりエディタ…

ピタゴラス方程式のようなものの解の数え上げ。ちょっとめんどくさそうだと思って放置していた問題。全然そんなことはありませんでした。何の工夫もない二重ループで十分。最初ピタゴラス方程式の互いに素な解を生成しながら DP かと思ったのですが、途中で…

108 解けました。解き方は分かってたけどやってなかっただけ。そして 110 も同じ方法で解けると思っていたらそうでもなかった。108 は n=1 から順番にメモしながら計算すればよかったのですが、110 は答えがわりと大きいのでもう少し頑張らないと無理でした…

前にやったとき途中で面倒になって放置していたんですが、今日やってみたらすぐ解けました。Lisp 使ったけど。連分数周りはよく分からない。展開していくとき √n の係数が必ず 1 になっているような気がするんですけど、証明できなかったし。

久しぶりに Porject Euler の問題が土曜日*1のうちに解けた気がします。今回は数学の知識を使わずに解ける問題でした。ちなみに 250 で "non-empty" という条件を見落とすといういつものケアレスミスで今回もしばらく悩みました。 *1:正確には日曜日になって…

解けました。漸化式はだいぶ前に作ってあったんですがそのまま放置してました。10^12 で mod 10^8 だから周期性を使うに違いない！と信じていろいろ考えた結果、周期を計算する方法を見つけました。実際の計算には計算機の力を借りる必要がありそうだったの…

ちょっと前までは先頭と末尾から解いていたんですが、最近 ascending difficulty で表示して上から解いてます。DP (or memoization) さえできれば楽なものが散見されます。だんだん Java 飽きてきたので Python でも使ってみようかな。

これはどう見ても DP だろー、と思ってそればっかり考えて、結局 DP したら 0.2sec とかで終わったんですが、forum を見ると brute force に近いやり方でも数秒程度できたようですね。頭に柔軟性が足りない。

problem 68 の forum で、コードを書かずに手で解くことについての話が出ていました。「正解を見つけること自体もだけど、それを解く速いアルゴリズムを実装するのも楽しみの一つじゃない？」「手で実行できる程度のアルゴリズムなら、コードを書くことはな…

Problem 61 が解けました。よく見たら brute force でも計算量はたいしたことないという問題。三角数から八角数まで四桁のものを全部並べてしりとりしてみたら、長さ 6 のものは 17300 通りぐらいしかありません。列挙できたら、条件を満たすかどうかをひと…

145 解きました。久しぶりに pencil/paper でした。forum をちょっと見てみましたが、pencil/paper か brute force の二択でしょうか。

確か年末にまとめて出た問題で、解答者が少ないやつなのですが、最近追加された Problem 233 がヒントなのではないかと思い始めました。結局二つの平方数の和で特別な形をしたものがいくつあるかという問題なので。

REPL で適当に計算してたらできたので submit しておきました。楽な問題。でも途中 2L11 と書くべきところを 2e11 と書いてはりました。前にもこんなことがあったような。

解けました。問題文の "What is the sum of all positive integers" を、なぜか "How many positive integers" の意味に解釈して二日ぐらい悩みました。ああもう。でも面白い問題でした。今まで解けた中では、数学的に一番高度な知識を使ったと思います。

Problem 101 見てたらあなごるの Polynomial Sequences 思い出して、人の解答読んだらこんな等式が成り立つことを知りました。ただし f の次数は n 未満。Lagrange interpolation とかいうものがあるらしいですが、それの別表現……なのかな？面白いと思ったの…

です。見出しだけで書きたいことが尽きてしまった。

この間までごちゃごちゃと書いていたやつに関係ある問題。道筋が見えてて最初の素因数分解をやる気になれば、 pencil/paper で解ける問題でした。私は一番最後のステップで計算ミスしまくって通らなかったので、結局二桁の整数を七つぐらい掛けるだけの簡単…

だいぶ前にみたときには手が出なかったような記憶があるのですが、今日考えてみたらそれほどでもありませんでした。冷静に考えれば。 となる組を見つけて枝刈り、とか考えるとはまります。ええ、はまりました。