Y箱

これも 103:シリーズです。

12個の数列について、ルール2がすでに満たされている場合、条件を満たすためには、ルール1について何セットの組み合わせをチェクしなければならないかという問題。

ルール1は、どのサブセットを取っても合計が違うということですが、ルール2から要素数が多い方が要素の合計が大きいことは確定なので、要素数が同じである場合だけ確認すればよいということになります。。
要素数が同じ2つの数列の和が等しいかどうか確認する必要があるのはどんなときか考えればよいということ。

「こういう選択をしたら同じになる可能性がある」か、「こういう選択をしたら片方が大きくなる」のどちらかの選択方法をみつければよい。
たとえば、1,2.3 と 10,11,12のぺあであれば、まあ、確実に後の方が大きいよね。

103のシリーズです。
これも去年の末に解いてますね。

沢山ある数列の中から、条件に合うやつを探す問題

(ルール1) 部分集合を全部作って、合計した値が同じものが無いかどうかチェック
(ルール2) 小さい方からと大きい方からできるだけ取るが、大きい方を1つ少なくした時に条件に合うかどうかチェック

ルール2の方はこれでいいかどうかちょっと不安だったけど、合ってたからよしとする。

これも去年の年末にやったやつです。

Fibonacci数列で、最初の9桁がPandigit(1-9を全て含む)で、最後の9桁もPandigitのものを探す問題。

Fibonacci数列を順に作って条件に合うかどうかチェックするだけですが、ちょっと工夫したと言えば、数字を文字列にするのってコストがかかるので、数字のまま取りだせる下9桁を先にチェックするようにしたところくらいでしょうか。

たいしたことやってないのに時間かかってます。

去年の末に解いたやつです。

条件に合う数列を新しく作る問題

これ、かなり悩んだ。 102を解いたあと、すぐに手を付けたんだけど、解きかたわからず/思いつかずで、放置している間に数年経ってしまった。
まあ<結局、初期の頃に思いついた、「全部やってみる」方式で解いてみることにして、実際やってみたら、時間はたいしてかからなかったという。

- 真ん中の数字を先頭にして新しい数列を作る
- 含まれる数を前後にいくつかずらした数列を全て生成
- 昇順になっていないものを除外

これで、候補を作って、条件に合うかどうかチェックというやりかた。

これも5年前に解いたやつだ。 思い出しながら書く。

内部に原点を含む三角形を判定する問題です。

外積を計算して同じ向きかどうかを判定しています。

久し振りにProject Eulerを解きました。
(※ なんと4年前に書いた下書きがそのままになっていた)

数列がはじめからN個与えられたときに得られる母関数では、N+1まで行くと間違った値(BOP)が出ます。 与える数列を増やしていったときに得られるすべてのBOPの和を求める問題です。

そういえば、こういうのって、補間法かなんか使えば出るんじゃなかったっけ…と思って解いたら解けました。
ウィキペディアで調べたら、ラグランジェ補間法ってやつだったので、まあ、そのまま、式にした感じです。

コメントにも書きましたけど、もうちょっとclojureらしく書いたほうがよかったのかもしれないんですが、そうすると、たぶん、元の式の形がなくなってしまいそう。

100個解くのを目標にしていたので、ひとまず目標は達成です。
これにあまり時間を取るのもなんなので、Project Eulerはしばらくお休みにします。

もうちょっと実用的ななにかをしないとということで、作りかけていたツールでも作ろうかと思っております。Herokuでwebアプリです。

あとは、core.logicもちょっとやってみたいと思っとります。

100番です。
袋から連続で2個のボールを取り出したときに、同じ色のボールが出る確率をちょうど2分の1にするには、何個のポールを入れたらいいでしょうか。という問題です。

初めに思いついた方法は時間がかかりすぎてだめでした。
式を立てていろいろいじっていたら解けました。

99番目の問題です。
ここに来て、問題ごとの難易度の差が激しいですね。

この問題はとても簡単。
思いつきでだーーっと書いたコードなので、あまりきれいではないのですが、直すまでも無いので、このままにしときます。

今回も内容についてのコメントは無し。

99番です。

アナグラムにあてはまる平方数についての問題です。
回答者数を見ると難しそうな問題だったのと、数独を解いた余波と、100達成に向けた勢いで、解説付きにチャレンジしました。

ほぼ、解いた手筋をなぞってます。

gistにソースつきで載せました。

解法としては、10分もかかってしまったので今一つですが、難しい問題ということで、よしとしときます。

大きな数の下10ケタを求める問題です。

2万人以上の人が解いている問題なので簡単です。

数独を解く問題です。

95を2月に解いて、それから取り組んでいたのですが、昼休みとか暇なときにしかやってないとは言え、なかなかタフで時間がかかりました。

結果的には、ネットからのデータの取得も含めて3.4秒ほどで解けたので上々でしょう。

95番です。友愛数の列をみつける問題です。

 2月に解いていたのに、なぜかここにエントリを作っていませんでした。 そんなわけで、どんな風に解いたのかうろ覚えなので、コードを読んで解説してみます。

辺の長さと面積が整数になる、「ほぼ正三角形」を見つける問題です。

始めに総当たりで解くやつを作ったら、10時間かかりました。さすがにこれはだめなので、恒例の逆から考えるパターンです。

4つの数字を加減乗除して作れる数を求める問題です。

しばらく考えてはみたのですが、総当たり以外にやりかたはなさそうなので、それで実装してます。
2分くらいかかってしまっていますが、まあ、よしとします。

数の各桁の数を二乗した和を並べた数が89でループする場合を数える問題です。

操作からすると、345と435と543などの同じ構成の数は同じ結果になるので、それをうまく使えばメモ化で速くなりそうなので、やってみた。

数を数列にしてソートする。0はなくても同じなので除外する。そうしてできた数列で判定する関数を作ってメモ化する。

解けたんだけど、遅い。

ふと、元の数をつくるのにどれくらいかかるか計算してみたら、それだけで2分近くかかってる。こりゃだめだ。 どうしよう。

格子点を使って直角三角形を作る問題です。

まずは、格子から2点を取って、原点合せた3点でできる三角形が直角を含むかどうかをチェックしてみたのですが、10分という想像以上の時間がかかってしまい、別解を考えました。
このとき、「直交するベクトルの内積は0になる」なんていうのを使ったのですが、かなり懐かしい感じでした。

ローマ数字の正規化？の問題です。

質問は、正規化したときにどれだけ文字数が減るかというものです。
解くにはいろいろ方法がありそうですが、問題の最後の一文に書かれている内容から置換対象が数個に限定されるので、それを数えることで直接減らせる文字数を数えています。

以下コードです。
簡単なので、解説無しです。

久し振りに進めました。

和と積が同じになる数列について、その個数ごとの最小のものをみつける問題。
仕事がいそがしかったせいもありますが、時間がかかりました。

苦労したので長ーい解説です。