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