PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 109 / ダーツ

問題の概要

ダーツをダブルアウト方式でプレイするとき,100点未満の状態からチェックアウトする方法は何通りあるか求めよ。
各回に得られる点数は1~20点の1倍(シングル),2倍(ダブル),3倍(トリプル)の他,ブルの25点,ブルのダブルの50点である。

本家:Problem 109 - Project Euler
日本語訳:Problem 109 - PukiWiki

解法

ダーツのルールを初めて知りました。

  • 最後は必ずダブル。
  • 最後以外の回はシングル,ダブル,トリプルどれでもいい。

この条件で3回(以下)の合計得点を99点以下にする方法が何通りあるか求めます。第31問と同様にべき級数を使いました。

variee.hatenadiary.com

6点の場合

問題文中で与えられている6点でチェックアウトする場合を考えます。素点が1点~4点の場合を考えればOKです。ダブルの級数は
 p_2=x^2+x^4+x^6+x^8

シングル,トリプルはそれぞれ次のようになります。
 p_1=x+x^2+x^3+x^4
 p_3=x^3+x^6+x^9+x^{12}

素朴に考えるとq=p1+p2+p3として
 q^2\times p_2+q\times p_2+p_2
を展開すればよさそうですが,この式を展開したときのx^6の係数は11ではなく14です。このズレの原因を調べるため,q^2*p2+q*p2+p2 の各項の6次の係数を見てみましょう。
以下,素点 x のシングル,ダブル,トリプルを Sx, Dx, Tx であらわし,最後の回の得点はカッコつきであらわします。

p2 の6次の係数1は
 6=(D3)
と対応。これは問題なし。

q*p2 の6次の係数4は
 2+4=S2+(D2)=D1+(D2)
 4+2=S4+(D1)=D2+(D1)
と対応。これも問題なし。

q^2*p2 の6次の係数は9。実際には次の6通りしかなく,ここで3個のズレが生じています。
 1+1+4=S1+S1+(D2)
 1+3+2=S1+S3+(D1)=S1+T1+(D1)
 2+2+2=S2+S2+(D1)=S2+D1+(D1)=D1+D1+(D1)

これは1回目と2回目の得点について次のようにダブルカウントしているためです。
 S1+S3+(D1)=S3+S1+(D1)
 S1+T1+(D1)=T1+S1+(D1)
 S2+D1+(D1)=D1+S2+(D1)

1回目と2回目の点のとり方が違う場合はこういう重複が起こり,同じ場合は起こりません。

1回目と2回目が同じ場合の多項式は
x^(1+1)+x^(1*2+1*2)+x^(1*3+1*3)
のような項の和です。一旦,これを q^2に足して2で割ることで重複を避けることに成功しました。

100点未満の場合

以上をもとに計算したところ,約0.2秒で終了。これが解答です。


一般の場合

ついでに全パターンを調べてみました。0点以上170点以下のチェックアウトの場合の数は次のようになります。

プロットすると2本の曲線のような変わったグラフになります。

f:id:variee:20180601014447p:plain

Project Euler 107 / 最短ネットワーク

問題の概要

頂点数40の重みつき有向グラフgが与えられる。その最小全域木をg'とする。gの重みの総和とg'の重みの総和の差を求めよ。

本家:Problem 107 - Project Euler
日本語訳:Problem 107 - PukiWiki

解法

頂点数7のとき

WeightedAdjacencyGraph でグラフを作り,FindSpanningTree で最小全域木を求めます。問題文中で与えられているサンプルでやってみましょう。

まずはグラフ作成。

f:id:variee:20180531161218p:plain

最小全域木は赤い点線のようになります。

f:id:variee:20180531161428p:plain

頂点数40のとき

同じ要領で頂点数40の場合を処理し,重みの総和の差を計算します。

約3秒かかっていますが,これはデータファイルをダウンロードしているためです。ローカルでやると0.004秒ほどで答えが出ます。

どんなグラフになるか

実際にどんな最小全域木ができるのか見てみましょう。

f:id:variee:20180531162455p:plain

元のグラフと重ねるとこうなります。

f:id:variee:20180531162510p:plain

Project Euler 607 / Marsh Crossing

Frodo and Sam need to travel 100 leagues due East from point A to point B. On normal terrain, they can cover 10 leagues per day, and so the journey would take 10 days. However, their path is crossed by a long marsh which runs exactly South-West to North-East, and walking through the marsh will slow them down. The marsh is 50 leagues wide at all points, and the mid-point of AB is located in the middle of the marsh. A map of the region is shown in the diagram below:

f:id:variee:20171205201150p:plain

The marsh consists of 5 distinct regions, each 10 leagues across, as shown by the shading in the map. The strip closest to point A is relatively light marsh, and can be crossed at a speed of 9 leagues per day. However, each strip becomes progressively harder to navigate, the speeds going down to 8, 7, 6 and finally 5 leagues per day for the final region of marsh, before it ends and the terrain becomes easier again, with the speed going back to 10 leagues per day.

If Frodo and Sam were to head directly East for point B, they would travel exactly 100 leagues, and the journey would take approximately 13.4738 days. However, this time can be shortened if they deviate from the direct path.

Find the shortest possible time required to travel from point A to B, and give your answer in days, rounded to 10 decimal places.

Problem 607 - Project Euler

Marsh = 沼地,湿地だそうです。

第一印象は「スネルの法則を使えば解けそう」でした。
「n*sin θ = (一定)」にしたがって曲がる経路が最短だろうと見当をつけましたが,スタートとゴールが決まっているので,この方法では解けません。
線分ごとの時間の和を求める方法で解きました。

全体を45度回転して,各点を
P1(-50/√2, -50/√2), P2(x1, -25), P3(x2, -15), P4(x3, -5),
P5(x4, 5), P6(x5, 15), P7(x6, 25), P8(50/√2, 50/√2)
と定め,移動速度を
v={10, 9, 8, 7, 6, 5, 10}
とします。必要な時間は
 f=\displaystyle \sum_{i=1}^7 \dfrac{P_i P_{i+1}}{v_i}

NMinimize で f の最小値を数値的に求めます*1

NMinimize ははじめて使ったのですが,変数の範囲を何も制約しないと0.05秒で,
-50/√2 < x1 < x2 < x3 < x4 < x5 < x6 < 50/√2
の制約をつけるとかえって遅くなって 0.2秒になるのが意外でした。

*1:最近の問題なので答えの数値は省略します。

算チャレ1036回を解いてみた

「算数にチャレンジ!!」さんの第1036回の問題を解いてみました。

2つの整数アとイがあります。アとイはともに1以上100以下の整数です。ア+イが偶数で,ア×2+イ×3 が5の倍数となるような(ア, イ)は何組あるでしょうか。
http://www.sansu.org/used-html/index1036.html

www.sansu.org

Mathematicaで解く

まずはそのまま解いてみました。答えは1000組。

妙にきれいな答えが出て不思議に思ったので,一般解も求めてみました。
連立合同式を Reduce すると
 x\equiv y\pmod{10}
が答えだとわかります。

1 ≦ x ≦10, 1 ≦ y ≦10 での解は

 x=y=k\quad (1\leqq k\leqq 10)

の10個。x, y それぞれに「+10」が10回ずつできるので,求める個数は

 10\cdot 10^2=1000\,\text{個}

となります。

手計算で解くなら

手計算で解く場合, 2x+3y\equiv 0\pmod{5} の 3 を -2 に変えることがポイントだと思います。

 2(x-y)\equiv 0\pmod{5}\quad \therefore x-y\equiv 0\pmod{5}

これだけで 1 ≦ x ≦10, 1 ≦ y ≦10 の解の候補が (1, 1), (1, 6) などの 2*10=20 個に減ります。「和が偶数」の条件でさらに半分の10個にしぼれて,これが 1 ≦ x ≦10, 1 ≦ y ≦10 の解です。あとは「+10」が10回ずつできることを使えば解けます。

Project Euler 293 / 擬似フォーチュン数

偶数の正整数 N は 2 の累乗であるか素因数がすべて連続した素数である場合,許容的と呼ぶ。最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である。

N が許容的であるとき,N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseudo-Fortunate number)と呼ぶ。

たとえば N=630 は許容的である。630 は偶数で,その素因数は連続する素数 2, 3, 5, 7 である。

631 より大きい次の素数は 641 であり,630 の擬似フォーチュン数は M=11 である。同様に 16 の擬似フォーチュン数は 3 である。

10^9 未満の許容的な数 N に対して, すべての異なる擬似フォーチュン数の合計を求めよ。

Problem 293 - Project Euler


問題文の流れは

  1. 許容的な数を求める
  2. 擬似フォーチュン数を求める

ですが,擬似フォーチュン数の方が簡単なのでこちらから書きました。
NextPrime を使います。


次に許容的な数を求めます。「10^9 未満」の条件から,使える素数は9個です。

「2だけ使った数の集合を作る」→「その各要素に3をかけたものの集合を作る」のような操作を繰り返して,最後に和集合をとります。
NestWhileList と AppendTo で書きました。

計算時間は約0.3秒で,許容的な数は6656個,相異なる擬似フォーチュン数は41個でした。ダブりまくりです。