Euler: Problem 106

Posted by YpsilonTAKAI On 2020年3月16日月曜日 0 コメント
これも 103:シリーズです。

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

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

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

ってなことを考えて、いくつか例を書いてみたんですが、思いついたのがこの方式。
READ MORE

Euler: Problem 105

Posted by YpsilonTAKAI On 2020年3月14日土曜日 0 コメント
103のシリーズです。
これも去年の末に解いてますね。

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

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

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

READ MORE

Euler: Problem 104

Posted by YpsilonTAKAI On 0 コメント
これも去年の年末にやったやつです。

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

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

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


READ MORE

Euler: Problem 103

Posted by YpsilonTAKAI On 0 コメント
去年の末に解いたやつです。

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

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

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

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

READ MORE

Euler: Problem 102

Posted by YpsilonTAKAI On 1 コメント
これも5年前に解いたやつだ。 思い出しながら書く。

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

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

READ MORE