「プロジェクトオイラー解説問142」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー解説問142」(2014/01/06 (月) 16:42:56) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*Problem 142 「完全平方数コレクション」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20142
x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.
*解法
この問題は深さ制限探索で解きます。
まず式を定義しなおします。
-x+y=S1
-x-y=S2
-y+z=S3
-y-z=S4
-x+z=S5
-x-z=S6
と定義します。（S1～S6は当然平方数）
探索を行うに当たってできるだけ早めに、(ｘ,ｙ,ｚ)の組が式の条件を満たすことが判明すれば答えが高速に見つかる希望が持てます。
まず深さ制限探索の上限を決めます。
x>y>zよりｘ+ｙが一番大きな数となるのでS1の上限を適当に定めます。（答えが見つからなかったらあとでS1を増加させてコードを再実行します）。
----
**前準備のメモ化
S1の上限をn1^2とするとS1は
S1=(4,9,16,,,,n1^2)の値をとります。
まずS1とS2はx+yとx-yですからｘはS1、S2から等距離にあることがわかりこれはS1とS2の平均です。
S1>S2,S1<=n^2となるS1、S2のすべての組み合わせでｘのリストを作りこれをｘｓとします。
x=(S1+S2)/2とｘを定義できます（当然ｘが整数となるものだけです）。
またyはy=s-S2と定義することができｘ、ｙの組が作れます。
ｘに対応するｙは複数得られｘの各値に対しｙのリストが空集合か1個以上のｙのリストが作られます。
これをメモ化しておきます。
----
ここで以下のような操作を考えます。
ys=f(x)をｘｓの要素ｘをｆ（ｘ）に一つ代入する操作と考えます。関数ｆは上のメモ化で求めたデータを基にｘの値から対応するｙのリストを返します。
次にysの要素を一つずつ試し要素をｙとします。
これでx+y,x-yの二つを満たすｘ、ｙの組み合わせが得られました。
ここでｆ（ｘ）にｘでなくｙを代入すると
zs=f(y)
とｙに対応するｚのリストが得られます。
zsの要素はどれもｙ+ｚ、y-zの両方を満たします。
このｚｓのリストから要素を取り出しｚとします。
この時点でこの(x,y,z)の組は
x+y,x-y,y+z,y-zの4つの条件を満たしていることが判明します。
あとはy+z,y-zが平方数ならこの(x,y,z)の組はすべての条件を満たしているのでｘ+ｙ+ｚの値を計算します。
すべての条件を満たす(x,y,z)の組でｘ+ｙ+ｚが一番小さくなったものが答えです。
もし答えが見つからなければS1の上限を大きくして再度コードを実行します。
ｘ+ｙ+ｚが見つかった場合それが最小であるとの確証を得るのも簡単です。
S1の上限n＾２を増加させたときS1=n^2で得られるｘの最小値ｘ1は
x１=(n^2+1)/2と定義されます。
このｘ1が見つかっている最小のｘ+ｙ+ｚより大きくなればそれ以上S1の上限を増加させてもｘ１は常にｘ+ｙ+ｚの答えより大きくなります。
よってx=(n^2+1)/2が見つかった答えより大きくなればこれ以上は検討する必要がないと判明します。
これは速度はまあまあですがメモリを多量に消費する解法です。
たぶんもっとエレガントな解法はあると思いますのでほかの方の解法も参考にしてください。
修正履歴
-2014/1/6 数式の記述ミスや記述のあいまいさを訂正。大体の記述はあってるはずなのでここで仮完成とする。
*Problem 142 「完全平方数コレクション」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20142
x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.
*解法
この問題は深さ制限探索で解きます。
まず式を定義しなおします。
-x+y=S1
-x-y=S2
-y+z=S3
-y-z=S4
-x+z=S5
-x-z=S6
と定義します。（S1～S6は当然平方数）
探索を行うに当たってできるだけ早めに、(ｘ,ｙ,ｚ)の組が式の条件を満たすことが判明すれば答えが高速に見つかる希望が持てます。
まず深さ制限探索の上限を決めます。
x>y>zよりｘ+ｙが一番大きな数となるのでS1の上限を適当に定めます。（答えが見つからなかったらあとでS1を増加させてコードを再実行します）。
----
**前準備のメモ化
S1の上限をn1^2とするとS1は
S1=(4,9,16,,,,n1^2)の値をとります。
まずS1とS2はx+yとx-yですからｘはS1、S2から等距離にあることがわかりこれはS1とS2の平均です。
S1>S2,S1<=n^2となるS1、S2のすべての組み合わせでｘのリストを作りこれをｘｓとします。
x=(S1+S2)/2とｘを定義できます（当然ｘが整数となるものだけです）。
またyはy=s-S2と定義することができｘ、ｙの組が作れます。
ｘに対応するｙは複数得られｘの各値に対しｙのリストが空集合か1個以上のｙのリストが作られます。
これをメモ化しておきます。
----
ここで以下のような操作を考えます。
ys=f(x)をｘｓの要素ｘをｆ（ｘ）に一つ代入する操作と考えます。関数ｆは上のメモ化で求めたデータを基にｘの値から対応するｙのリストを返します。
次にysの要素を一つずつ試し要素をｙとします。
これでx+y,x-yの二つを満たすｘ、ｙの組み合わせが得られました。
ここでｆ（ｘ）にｘでなくｙを代入すると
zs=f(y)
とｙに対応するｚのリストが得られます。
zsの要素はどれもｙ+ｚ、y-zの両方を満たします。
このｚｓのリストから要素を取り出しｚとします。
この時点でこの(x,y,z)の組は
x+y,x-y,y+z,y-zの4つの条件を満たしていることが判明します。
あとはｘ+z,ｘ-zが平方数ならこの(x,y,z)の組はすべての条件を満たしているのでｘ+ｙ+ｚの値を計算します。
すべての条件を満たす(x,y,z)の組でｘ+ｙ+ｚが一番小さくなったものが答えです。
もし答えが見つからなければS1の上限を大きくして再度コードを実行します。
ｘ+ｙ+ｚが見つかった場合それが最小であるとの確証を得るのも簡単です。
S1の上限n＾２を増加させたときS1=n^2で得られるｘの最小値ｘ1は
x１=(n^2+1)/2と定義されます。
このｘ1が見つかっている最小のｘ+ｙ+ｚより大きくなればそれ以上S1の上限を増加させてもｘ１は常にｘ+ｙ+ｚの答えより大きくなります。
よってx=(n^2+1)/2が見つかった答えより大きくなればこれ以上は検討する必要がないと判明します。
これは速度はまあまあですがメモリを多量に消費する解法です。
たぶんもっとエレガントな解法はあると思いますのでほかの方の解法も参考にしてください。
