数学プログラミング・チャレンジに挑戦しました

CodeIQの出題者だった@riverplusさんの「数学プログラミング・チャレンジ」に挑戦しましたので、ネタバレです。

riverplus.hatenablog.com

問題と解説

これまでのCodeIQのプログラミング問題サービス終了に伴い、未出題のネタ5問が一挙に出題されました。以下、1問ずつ見ていきます。

第1問:「メダルツアー」問題

問題と解説

幅w、高さhの格子で、左からm番目の縦の道全て(格子点の間h本)にメダルが置いてある状況で、 左下の点から右上のゴールまで最短距離で向かう。 この時、取り得る経路を等しい確率で選ぶ場合の、道中にあるメダルの個数の期待値を$F(w,h,m)$とする。 $F(10,10,3)$の値を、小数点以下が7桁になるように四捨五入して求めよ。

答え: 0.9090909

解説

これは素直に数式一発です。

$$ F(w,h,m)=\frac{1}{{}_{w+h}C_w}\sum_{i=1}^h {}_{m-1+i-1}C_{m-1}\cdot {}_{w-m+1+h-i}C_{w-m+1} $$

適度に階乗に直して総和を求めれば答えが出ます。計算するRubyコードは次のようになります。

第2問:「奇数和平方数」問題

問題・解答

自然数nに対し、その総和が平方数となる、連続する幾つか(1つ以上)の奇数の組み合わせで、その最大値がn以下のものの組数を$F(n)$とする。 $F(10^7)$の値を求めよ。

答え: 27368012

解説

1から連続する奇数の和というのが平方数になるのは良く知られていることかと思います。ということは、連続する幾つかの奇数の和は、平方数の差になることが分かります。

ということは、この問題は、

  • $1\le c\le\frac{n-1}{2}$ で $c^2-a^2=b^2~( a\ge 0, b\gt 1 )$ を満たす整数$(a,b,c)$の組の数を求めよ

という問題に還元することができます。

ということはピタゴラス数を数えれば良いわけで、今回はベタに$(g\cdot 2ud, g\cdot(u^2-d^2), g(u^2+d^2))$ ( u,dは互いに素、偶奇不一致 ) の組み合わせを数えることにしました。u,d の2重ループ毎に g の最大値 t を足し合わせればそれで計算できます。なお、a=0 となるケースだけは別にカウントしておきます。

Rubyでの実装は次のようになります。

第3問:「ヒストリー和」問題

問題・解答

自然数kに対し、数列$F_k(n)$を次のように定義する。

$$ F_k(n)=\begin{cases} 0 & ( n\lt 0 ) \\ 1 & ( n=0 ) \\ \sum_{i=1}^k (k-i+1)F_k(n-i) & ( n>0 ) \end{cases} $$ この時、$F_{10}(10^{10})+F_{10^4}(10^6)$ の下8桁を求めよ。

答え: 55170008

解説

線形の漸化式が与えられている訳ですが、k の値が小さければ行列のべき乗をバイナリ法でこなせば速く計算できる一方で、k が大きくなるとその手は使えません。

しかし、

$$ \begin{eqnarray} F_k(n)&\,& &=&kF_k(n-1)&+&(k-1)F_k(n-2)&+\cdots+&F_k(n-k)&\,& &~&(n\gt 0) \\ &\,&F_k(n-1)&=& &\,&kF_k(n-2) &+\cdots+&2F_k(n-k)&+&F_k(n-k-1)&~&(n\gt 1) \end{eqnarray}\\ \Rightarrow F_k(n)=(k+1)F_k(n-1)-F_k(n-2)-F_k(n-3)-\cdots -F_k(n-k-1)~ ~ ~(n\gt 1) $$ $$ \begin{eqnarray} F_k(n)&\,& &=&(k+1)F_k(n-1)&-&F_k(n-2) &-&F_k(n-3)&-\cdots -&F_k(n-k-1)&\,& &~&(n\gt 1) \\ &\,&F_k(n-1) &=& &\,&(k+1)F_k(n-2)&-&F_k(n-3)&-\cdots -&F_k(n-k-1)&-&F_k(n-k-2)&~&(n\gt 2) \end{eqnarray}\\ \Rightarrow F_k(n)=(k+2)(F_k(n-1)-F_k(n-2))+F_k(n-k-2)~ ~ ~(n\gt 2) $$

と整理すれば、バイナリ法は使えないものの、項数を大幅に減らして計算できます。

ということで、k の大きさに合わせて2種類の計算をハイブリッドしたRubyでの実装です。

第4問:「ラディカル和」問題

問題・解答

自然数nに対し、nの互いに異なる素因数の積を$F(n)$、 自然数mに対し、1~mの範囲のnに対する$F(n^2+1)$の和を$G(m)$とする時、 $G(2\times 10^6)$の値を求めよ。

答え: 2424282424390823376

解説

単純に考えれば、1~m の範囲の n それぞれで $n^2+1$ を素因数分解して、各素因数の積を計算すれば良いわけですが、都度素因数分解していたらどれだけ時間がかかるか分かりません。( というか$O(m^2)$でしょうか )

そこで、素因数が現れる周期を管理することにします。例えば素因数5を持つ$n^2+1$であれば、n=2 の時に初めて現れ ( 2^2+1=5 )、対になる 3 が判明し ( 5-2=3 )、以降は $5k+2, 5k+3$ の5周期で現れていくわけです。
なので、例えば $n=12$ で5の倍数を引いたら次は +5 した 17 をタイマーとしてセットしておくような感覚で管理するわけです。これにはヒープかもしくはC++のpriority queueが使えます。 新しい素因数が現れたら、新しい周期を更に管理に組み込んでいく感じです。

ということで、C++の実装は次のようになります。…priority queue 使うためにしかC++使ってない気もしますがキニシナイ。

第5問:「10/16数」問題

次の条件を満たす自然数を10/16数と定義する。

  • その数の10進表記をそのまま16進表記と見做した数が、元の数の整数倍である

100番目に小さな10/16数を求めよ。

答え: 753663475455

解説

各桁の満たす条件を探る方針では巧く行く気がしなかったので、それなりに効率よく探索できるように、という観点で攻めました。

例えば、5桁の数の中で最上位が1である数 ( 1xxxx ) を対象とした場合を考えてみます。

そうすると、次の桁として使えるものは? と考えて絞り込んでいくわけですが、ここで 11xxx と 1 を選択したとすると、倍率 (16進表記と見做した数)÷(元の数) の範囲は、未確定の部分を全部 0 にした場合と 9 にした場合で見積もることができます。

  • 11999: 11999(16)÷11999(10)=6.0079…(10)
  • 11000: 11000(16)÷11000(10)=6.3301…(10)

全部 9 にする時が倍率は最小です。ということは、11xxx という数に関しては、倍率は 6~7 の範囲なので整数倍を満たせない ( なので却下 ) ということが分かります。なお、1xxxx で倍率が整数となり得るのは 12xxx ( 12999: 倍率5.8608…、12000: 倍率6.144 ) だけです。

…ということを、上位の桁から次々見て行けば、ダメな候補をある程度早い段階で捨てることができるはずです。

実際にRubyで実装したのが次のコードになります。最終的な答えは12桁ですが、1秒もかかっていないので、まあなんとかなっているようです。

終わりに

5問一気に解説書くのは辛かった…! ので少々手抜き感が否めませんがご容赦を。最初は問4から入って、最後問5で締めたのですが、この2問が方針決定的にもコード的にも苦しみました。

これで本当に終わりかと思うと寂しいところではありますが…。最後まで面白い問題を有難うございました。