Project Euler P104

  • 投稿日:
  • by

Project Euler Problem 104 Pandigital Fibonacci ends

両端がパンデジタルなフィボナッチ数は? な問題でした。単純に足していったら桁が足りないだろうと。

ですのでメモリーはもったいないですが、intの長い配列を作って、足し算する関数を作って足していき、両端がパンデジタルかどうか判定して返しました。

みにくい方法ですので、他に方法があるはずです。こちらもフォーラムの掲示板に張り付きます。

Project Euler P103

  • 投稿日:
  • by

Problem 103 Special subset sums: optimum

条件 :

数列を、二つの、重複していない部分集合B,Cに分ける。

1. 作成した部分集合の合計が同じではならない。
2. もしBの要素数がCより大きかったら、S(B)>S(C)である。

\(n+1 = {b,a_1+b,a_2+b,...a_n+b}\)で作れるっぽいけれども、違うよね、n=7の時の数列を文字列にして回答してね、な問題文でした。

じゃあ別の方法があるかなーと考えたのですけれども、思いつかなくて。解説をググりました。すると、\(n+1 = {b,a_1+b,a_2+b,...a_n+b}\)で作った数列から、+-幾つを足したり引いたりして探していました。

ですので6重ループでゴリ押しってしまいました。部分集合を作る関数は、二進数で作りました。正答の数字は出せましたが、フォーラムの掲示板を見てスマートな方法を考えます。

Project Euler P102

  • 投稿日:
  • by

Project Euler Problem 102 Triangle containment

三角形の頂点がファイルに格納されており、原点を含む三角形の数を数えよ、な問題でした。

ゲームの当たり判定で行けないかな? と検索。点と三角形の当たり判定( 内外判定 ) が引っかかりました。

三角形の内側に点がある時、点と各頂点を結ぶベクトルと各辺のベクトルの外積ベクトルは三つとも同じ方向を向く、三角形の外側に点がある時、外積ベクトルの向きは揃わない、だそうです。

ベクトルの外積の求め方が分からないので検索しました。 ベクトルの外積の定義、図形的な意味、微分の公式が引っかかったので実装。

向き(z成分)だけ分かればいいので、\(z=x_1*y_2 - y_1*x_2\)で外積のz成分だけ計算して、三つの計算結果の向きが揃っていたら原点を含む、揃っていなかったら原点を含まない、でカウントしました。

Project Euler P101

  • 投稿日:
  • by

Project Euler Problem 101 Optimum polynomial

どうやってk=2,3,4...の時の式を求めるかなーと。こしょこしょ書いていました。すると、n連1次方程式で解けるなーと気づきました。

k=2、\(OP(2,n)=7n-6\)は、

k=1 : \(a+b=1\)
k=2 : \(2^1a+b=8\)

\(a+b=1\)
\(2a+b=8\)

a、bを求め、7n-6を求めました。右辺は生成関数\(n^3\)にkを代入した1,8です。

k=3、\(OP(3,n)=6n^2-11n+6\)は、

k=1 : \(a+b+c=1\)
k=2 : \(2^2a+2^1b+c=8\)
k=3 : \(3^2a+3^1b+c=27\)

\(a+b+c=1\)
\(4a+2b+c=8\)
\(9a+3b+c=27\)

から\(6n^2-11n+6\)と鉛筆で書き、これで出せるなーと。

n連1次方程式をプログラムで解く方法は? とインターネットで検索した所、ガウスの消去法が引っかかりました。

ガウスの消去法

ガウスの消去法による連立一次方程式の解き方

例解を鉛筆でガウスの消去法で解いて、解けたのでプログラムにし、例解を通しました。

例解を通したので、問題の生成関数\(u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}\)を解いてみて、数字が通りました。

間を空けてメモを書いているので曖昧なメモになりました。解いたらすぐにメモを残します。

Project Euler P100

  • 投稿日:
  • by

Arranged probability Problem 100
If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

箱の中に青いディスクが15個、赤いディスクが6個入っていて二回続けてディスクを取り出した時、取り出した両方のディスクが青の確率は\(\frac{1}{2}\)である。

次にこの確率が\(\frac{1}{2}\)になるディスクの数は、青が85個、赤が35個である。ディスクの総数が\(10^{12}\)を初めて超える場合の青のディスクの枚数を答えよ。

で、考えました。ディスク全部の数をALL、青のディスクをBLUEとすると、

\(\frac{BLUE}{ALL} * \frac{BLUE-1}{ALL-1} = \frac{1}{2}\) です。\(BLUE^2 - BLUE - \frac{1}{2}(ALL^2+ALL)\)で、二次方程式の解の公式\(\frac{1±\sqrt{b^2-4ac}}{2}\)より、BLUE=\(\frac{1±\sqrt{1^2-4*1*\frac{1}{2}(ALL^2+ALL)}}{2}\)で、\(\sqrt{1+2*(ALL^2+ALL)}\)が整数になるALLを\(10^{12}\)からインクリメントして探しました。

すると随分帰ってこなくて。インクリメントじゃ駄目だなーと。分からないので調べました。するとペル方程式に帰着させる、と解説されていたので解説を読みました。

http://projecteuler.net/index.php?section=problems&id=100

\(\frac{BLUE}{ALL} * \frac{BLUE-1}{ALL-1} = \frac{1}{2}\)
\(\frac{BLUE^2-BLUE}{ALL^2-ALL} = \frac{1}{2}\)
\(BLUE^2-BLUE = \frac{ALL^2-ALL}{2}\)
\(2BLUE^2-2BLUE = ALL^2-ALL\)

平方完成して、

\(\frac{1}{2}(2BLUE-1)^2 - \frac{1}{2}= \frac{1}{4}(2ALL-1)^2 - \frac{1}{4}\)

両辺に4を掛けて、

\(2(2BLUE-1)^2 - 2= (2ALL-1)^2 - 1\)

移項して、

\(-2 = (2ALL-1)^2 - 2(2BLUE-1)^2 - 1\)
\(-1 = (2ALL-1)^2 - 2(2BLUE-1)^2\)
\((2ALL-1)^2 - 2(2BLUE-1)^2 = -1\)

(2ALL-1)=X、(2BLUE-1)=Yと置き、

\(X^2 - 2Y^2 = -1\)

の形式のペル方程式。2ALL-1,2BLUE-1の形式なのでそれぞれ奇数。

上のページで、ペル方程式の次に漸化式が記述されているのですが、漸化式の求め方が分からなかったのでググりました。

http://www.geisya.or.jp/~mwm48961/kou3/diophantine2.htm

こちらのページより、

\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}
a & Db\\
b & a\end{pmatrix}\binom{x_n}{y_n}\)

a=Xの最小の値、
b=Yの最小の値、
D=Yの係数

だそうなので

\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}
1 & 2\\
1 & 1\end{pmatrix}\binom{x_n}{y_n}\)

行列の掛け算は、

\(\begin{pmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{pmatrix}\binom{b_1}{b2}=
\begin{pmatrix}
a_{11}*b_1 + a_{12}*b_2 \\ a_{21}*b_1 + a_{22}*b_2
\end{pmatrix}\)

なので、

\(\begin{pmatrix}
1 & 2\\
1 & 1\end{pmatrix}\binom{X_n}{Y_n}=
\begin{pmatrix}
X_n + 2Y_n \\ X_n + Y_n\end{pmatrix}\)

\(X_{n+1}=X_n+2Y_n\)
\(Y_{n+1}=X_n+Y_n\)

を漸近式として出しました。これで\(X_n\)と\(Y_n\)から\(X_{n+1}\)と\(Y_{n+1}\)を計算しつづけます。

(2ALL-1)=X、(2BLUE-1)=Yと置いたので、

\(ALL=\frac{X+1}{2}\)
\(BLUE=\frac{Y+1}{2}\)

XとYは奇数なのでXとYが奇数の場合のみALLとBLUEを計算して、ALLが初めて\(10^{12}\)を超えた時のBLUEを計算して表示。試しで通した所、通りました。

間違いを書いていたらごめんなさい。以上メモです。

Project Euler P98

  • 投稿日:
  • by

Project Euler P98 Anagramic squares

アナグラムの問題でした。最初、文字を入れ替えて意味のある言葉=アナグラムになるのをどうやって判定したらいいのかなーと。問題を読み返したらアナグラムはすべてファイルに含まれている、と書かれていたので、ファイル内のワードでアナグラム判定。

next_permutationで入れ替えて探していたのですけれど時間がかかって。思いついたら、ワード内の文字列を辞書順でソートして同じならアナグラムです。それでアナグラムを判定してリストに格納してリストをマップに格納しました。

これに数字を当てはめて、両方共平方数のを探す処理を書きました。平方数判定するのに予め平方数をマップに格納。後は数字の当てはめです。

0,1,2,3,4,5,6,7,8,9をnext_permutationで入れ替えて、文字数分左から取って総当りしました。プログラムを流したら同じ数字が並びました。重複して処理しているのでした。例えば四文字取る際に、1,2,0,4,5,6,7,8,9と1,2,0,4,9,8,7,6,5、です。

3文字の数字列、4文字の数字列...と前もって作ろうかなーと思いながら流しました。数字は出たので、これで通らなかったら数字列を前もって作ろうと確認したら正答で通ったのでそのまま次の問題に進みました。

より早く出来るよなー、です。

Project Euler P96

  • 投稿日:
  • by

Project Euler Problem 96 Su Doku

数独の問題でした。数独のルールが分からないのでWikiPediaで調べました。

縦と横に同じ数字が現れてはならない、3x3のマスの中に同じ数字が現れてはならない、0に数字を埋めよ、な問題でした。

WikiPediaに解法が載っていて、既に埋まっている数字の横と縦には同じ数字はこないので、それで縦一直線、横一直線をその数字を借り埋めして、空いているマスが一つならそこで確定、だそうでした。

まずは上のロジックを実装しました。帰ってこなくて、盤面を見たら3x3のマスの中で0が一つ埋まっていない所で無限ループに入っていました。0が一つなら残りの数字で埋められます。埋めました。

多分3x3のマスの中で0が2個以上なら分岐して探索しないといけないだろうなーと思っていた所、0が2個以上で解けなくて帰ってきました。ですので3x3のマスの中で0を数えて総当りで埋めて探索。なかなか帰ってきませんでした。

ぼんやりと解いている盤面を見たり、解けた盤面判定のメソッドを書いていたら、横一行は1-9が一度だけ現れる行、縦一列も1-9が一度だけ現れる列で解かれていると気づきました。

ですので、3x3のマスに注目する方向から転換し、横一行に注目する方向に。一行目から見て、0の場所と、埋まっていない数字を一覧。縦に同じ数字がない組み合わせで仮決め。他にも埋められる組み合わせがあるかもしれないので再帰で分岐。Grid3、Grid4と埋められたのですが、時間がかかって。

ありえない埋め方に突き当たったらその線はないので、再帰を打ち切ろうと。まず、3x3のマスに注目して0を埋められる組み合わせが一つも見つけられなかったら詰んでいるのでその探索は打ち切り。

また、3x3のマスに同じ数字が入っていたらこちらもルールに則っていないので探索を打ち切り。

そんなロジックを組んで、何十分か流していたらGrid50まで通りました。左上の数字を三桁の数字に変換して合計。試しで答え合わせをしたら通りました。

振り返ると、全探索と枝刈りをやっていたのでした。チーター本や蟻本で読みましたが、自分が実際にやってみると骨だなー、と。

また、探索を打ち切るメソッドのスピードを早くしたり、探索を打ち切る判断を賢くすればさらにプログラムが早くなるでしょう。精進です。