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まで通りました。左上の数字を三桁の数字に変換して合計。試しで答え合わせをしたら通りました。

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

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

Project Euler P95

  • 投稿日:
  • by

Project Euler P95 Amicable chains

友愛鎖で、要素が1,000,000を超えない鎖で最長の鎖の最小のメンバーを返せ、な問題でした。

友愛数を求めるので、素因数分解じゃなくて因数の一覧だなー、とドンキーにループで割って友愛数を計算する関数を作成。

鎖を下からドンキーに1,000,000まで計算。途中で1,000,000を超える鎖なら次の数に。

計算したところ、帰ってこない数字が。見たら途中でループしていました。マップでループを検知して次の数字に。

途中で随分長い鎖が出てきて、これかなーと眺めていたのですがドンキーに999,999まで計算しました。結局、途中で出てきた長い鎖の最小のメンバーで試したら通りました。

次は数独です。数独のルールがそもそもわからないなー、と数独のルールを眺めています。まずは手でやって、それからプログラムに落とし込みます。以上メモです。

Project Euler P94

  • 投稿日:
  • by

Project Euler P94 Almost equilateral triangles

最初問題文を読んだとき、1万人を切るような難しい問題かな? P93の次だから飛ばされたのかな? と。周囲が1,000,000,000までなら3で割って、とループの上限を設定。

1引くのと1足すので計算。それぞれ面積を計算。浮動小数点の計算怖かったのでなるたけ近い数字で計算するように、とヘロンの公式で計算して整数になるか判定して集計。通りませんでした。

ドンキーに底辺を1/2して、三平方の定理で三角形の高さを求めて三角形の面積を計算して整数になるか判定して集計しても通らなかったのと、ヘロンの公式を使ったのと結果が違いました。

計算ミスしてるかなー、そちらを追うかなーと思ったのですが、そもそもで浮動小数点怖い、と。整数で計算する方に倒しました。

1. 底辺 % 2が0じゃなかったらそもそもで面積は整数にならない

2. 高さが整数にならなかったら面積は整数にならない。浮動小数点取らない方針なので、予め整数の二乗マップを作って、斜辺^2 - (底辺/2)^2 が整数の二乗マップになかったら高さは整数にならない

3. 底辺*高さ % 2が0じゃなかったら面積は整数にならない

で判定して数えました。特に二乗マップの生成で時間がかかりましたが、正答の数字は出せました。以上メモです。

Project Euler P93

  • 投稿日:
  • by

Project Euler P93 Arithmetric expressions

1万人切りだから難しいだろうなーと。問題文を読んでわからなかったのでアイディアを書き出しました。

カッコの組み合わせを書き出して。これリテラルで行けないかな...? とリテラルで行くことに。

(1 2) 3 4

(1 2 3) 4

((1 2) 3) 4

(1 (2 3)) 4

的にリテラルで。((1 2 3) 4)的に数字が三つ以上並ぶ場合は*,/を優先して+,-を後回しに。

1,2,3,4から6,7,8,9までの数字列を四重ループで作成。next_permutationで順列を総当りして計算。

計算してみたら、同率が二つ。二つの数字を試したら片方が通りました。通りましたが通った内に入らないだろうと見直し。

問題文に帰って考えました。

14 = 4 * (3 + 1 / 2)

ですが、1/2で0.5になっています。3.5*4=14。途中で小数になったら例外を投げて次の計算に飛ばしていましたが、途中で小数になっても最後に整数になる場合もありました。

ですので途中で整数になっても中断せずに計算し、結果が整数だったら結果マップに格納。それで正答が出せました。メモです。

ProjectEuler P91

  • 投稿日:
  • by

Project Euler Problem 91 Right triangles with integer coordinates

三角形の三つの頂点の内、一つの頂点を(0,0)で固定。他のp1(x1,y1),p2(x2,y2)の座標を、四重ループで総当り。

二点の距離から三辺を求めました。√(xa-xb)^2+(ya-yb)^2ですが、ルートを取ってdoubleになるのが嫌だったのでルートは取らずに。

一番長い辺を判断して、三平方の定理により一番長い辺の長さの二乗=他の辺その1の長さの二乗+他の辺その2の長さの二乗 だったら直角三角形と判断。

p1(x1,y1),p2(x2,y2)がひっくり返っているのを重複して数えたので最後に2で割りました。