PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 315 / デジタルルート時計(2)

前回の記事の続きです。Sam と Max の表示コストをそれぞれ計算して差をとるかわりに,両者の差だけ計算します。

variee.hatenadiary.com

桁ごとのコスト差

表示がないことをΦであらわします。ある桁の表示が a から b に変わるとき,Sam は「a→Φ→b」,Max は「a→b」と推移するので表示コストの差は次の形の式で求められます。

 g(a,\, b)=f(a,\, \phi)+f(\phi,\, b)-f(a,\, b)

全体としての差

この問題では 10^7 以上 2*10^7 以下の数が相手なので,時計の表示は次のように変化します。最高でも3回しか推移しません。

  1. 8桁の数
  2. 1+9*7=64以下の数(2桁以下)
  3. 7+9=16以下の数(2桁以下)
  4. 1桁の数

最初に8桁の数を表示するところでは差は生じません。また,8桁→2桁のとき Sam も Max も上位6桁は「a→Φ」型の変化をするので,ここでも差は生じません。
元の数を n,各位の数字の和を f(n) であらわすと

 n→f(n)→f^2(n)→f^3(n)

のかわりに

 \bmod(n,100)→f(n)→f^2(n)→f^3(n)

を考えればいいことになります。

実装

問題文には 10^7 という大きな数が書いてありますが,実際に相手にするのは2桁以下の数から2桁以下の数へ変化するときのコスト差です。

「1桁→2桁」(最初だけおこりうる),「2桁→2桁」,「2桁→1桁」の各場合に対応できる関数を書いてできあがりです。約10秒でした。