「今週のお題:ダイヤルロックを解除して!」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力から空白区切りで m,n が与えられるとき、次の場合の数を出力する。
  • 0~9の数字が刻まれたダイアルを左右交互に、合計n目盛り分回して m 桁の数字を合わせて開錠するタイプのダイヤルロックの、数字の組合わせ。
  • なお、必ず 0 の状態から左回しで始め、最初の数字は 0 以外になること。また明記はされていなかったが、次の数字に合わせる時に1周以上 回すことはしない。

うちのポストなんかもこのタイプの錠になってますね。次の図は問題の例として載っていたものですが、528 の3桁に合わせる時のダイヤルの動きを表しています。

https://codeiq.jp/sites/default/files/answer_ready/3233/q78.png

解説

次のRubyのコードを提出しました。

p ->m,n{
  imax=(n-m)/9
  # mHi
  fc,mc=->i{
    mc[i]||=fc[i-1]*(m+i-1)/i
  },[1]
  # mH(n-9*i)=(m+n-9*i-1)C(m-1)
  fg=->i{
    b=n-m-9*i
    (1...m).reduce(1){|s,j|s*(b+j)/j}
  }
  ff,mf=->i{
    mf[i]||=fg[i]-(i+1..imax).reduce(0){|s,j|s+ff[j]*fc[j-i]}
  },[]
  ff[0]
}[*gets.split.map(&:to_i)]

結局求める答えは、次の数までダイヤルを回す目盛りの数 $a_j$ に関して、$a_1+a_2+\cdots+a_m=n\,\,( 1\le a_j \le 9 )$ の解の個数です。

ここで、$a_j \le 9$ の制約を無視すれば、重複組み合わせ ${}_mH_{n-m}$ によって計算できるのですが、$n$がある程度大きい場合には、9を超える $a_j$ が含まれる組み合わせの分がありますから、不適切です。

そこで合計を 9 刻みに変化させ、 $$ \begin{eqnarray} f(i)&=&( a_1+a_2+\cdots+a_m=n-9i ( 1\le a_j \le 9 ) の解の個数 )\\ g(i)&=&{}_mH_{n-m-9i} \end{eqnarray} $$ と置くと、9超えの要素をどのように配置するかに着目することで $$ f(i)=g(i)-{}_mH_1\cdot f(i+1)-{}_mH_2 \cdot f(i+2)-\cdots $$ という関係式が成立し、この$f(0)$が答えとなります。

上の実装は、これをメモ化再帰で実装したものです。

なお、式は無限和の形で書いていますが、実際には$i$がある程度大きくなったところで解の個数が 0 になるので、そこまでで評価を打ち切るようにしています。

終わりに

1桁ごとに目盛りを1~9動かすような動的計画法と迷いましたが、重複組み合わせで一気に計算できた方がお得かな? と考え、今回の実装にしました。実際どうだったんでしょうか。