「ディビジョン・ナイン」問題解答 ( CodeIQ )

はじめに

CodeIQというところでプログラミング問題「ディビジョン・ナイン」に解答しましたので、ネタバレです。

codeiq.jp

問題

入力 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にまとめができました。他の方のコードも色々面白いので是非参考に。

togetter.com

(追記終わり)