「ディビジョン・ナイン」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「ディビジョン・ナイン」に解答しましたので、ネタバレです。
問題
入力 n に対して、以下で定義される関数$F(n)=$「各桁が全て1~4の10進$n$桁の数の個数」の値を出力する、という問題です。なお、1~4 の中で使ってない数字がある場合も個数に含めます。
解説
最初は、次のRubyのコードを提出しました。
require 'matrix' M=Matrix[ [0,0,0,0,0,1,1,1,1], [1,0,0,0,0,0,1,1,1], [1,1,0,0,0,0,0,1,1], [1,1,1,0,0,0,0,0,1], [1,1,1,1,0,0,0,0,0], [0,1,1,1,1,0,0,0,0], [0,0,1,1,1,1,0,0,0], [0,0,0,1,1,1,1,0,0], [0,0,0,0,1,1,1,1,0] ] puts (M**gets.to_i)[0,0]
すっごくベタですが、次の数式をそのままコード化したものです。
$$ F(n)= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} $$
なぜかというと、「9で割った余り」に着目すると分かります。
「ある数が9で割り切れるかどうか」は、「( 10進数としての ) 桁の合計が9で割り切れるかどうか」で調べることができるのは有名な話ですが、もう一歩踏み込むと、「ある数を9で割った余り」=「桁の合計を9で割った余り」であることも分かります。
ということは、例えば 12345 (余り6) と 1234 ( 余り1 ) を文字列的に連結した 123451234 の余りは、6+1 mod 9 で 7 というように。桁を分割して再帰的に処理することができることを意味します。今回桁に使える数字は1~4だけですから、
- {9で割り切れるn桁の数}={余りが5のn-1桁の数に4をつなげた数}∪{余りが6のn-1桁の数に3をつなげた数}∪{余りが7のn-1桁の数に2をつなげた数}∪{余りが8のn-1桁の数に1をつなげた数}
といった具合に。
そこで、9で割り切れる数の個数$F(n)$だけでなく、9で割った余り1~8に対応する個数$F_1(n)$~$F_8(n)$ も設けると、次の漸化式が成立することが分かります。
$$ \begin{pmatrix} F(n) \\ F_1(n) \\ F_2(n) \\ F_3(n) \\ F_4(n) \\ F_5(n) \\ F_6(n) \\ F_7(n) \\ F_8(n) \end{pmatrix}= \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \end{pmatrix} \begin{pmatrix} F(n-1) \\ F_1(n-1) \\ F_2(n-1) \\ F_3(n-1) \\ F_4(n-1) \\ F_5(n-1) \\ F_6(n-1) \\ F_7(n-1) \\ F_8(n-1) \end{pmatrix} $$
…ということで、冒頭の行列演算で計算できる、ということなのですが。
ただベタ過ぎて文字数的に全然なので、ちょっと考え直して次のRuby(82)で再提出しました。
v=[0]*8<<1 gets.to_i.times{v,t=[0]*9,v;36.times{|i|v[i%9]+=t[(i+1+i/9)%9]}} p v[8]
係数行列を疎行列と見て、漸化式である行列・ベクトル積を計算するものですね。( ベクトルの要素の順序は、上の数式とは逆になっています )
アルゴリズム的にはこれで計算量$O(n)$なので、特に速度的には気にする必要もなく…。行列のべき乗なら$O(log(n))$にできますが、そっちの方面では特に頑張っていません。
終わりに
行列は強力だなあ、という感想しかない問題ですね。ただ、もうちょっと短い実装があるようなのですが、あまり突き詰められずに終わってしまったのが心残りです。
(2016/4/8追記)
いつもの通り、togetterにまとめができました。他の方のコードも色々面白いので是非参考に。
(追記終わり)