「今週のお題:ダイヤルロックを解除して!」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力から空白区切りで m,n が与えられるとき、次の場合の数を出力する。
- 0~9の数字が刻まれたダイアルを左右交互に、合計n目盛り分回して m 桁の数字を合わせて開錠するタイプのダイヤルロックの、数字の組合わせ。
- なお、必ず 0 の状態から左回しで始め、最初の数字は 0 以外になること。また明記はされていなかったが、次の数字に合わせる時に1周以上 回すことはしない。
うちのポストなんかもこのタイプの錠になってますね。次の図は問題の例として載っていたものですが、528 の3桁に合わせる時のダイヤルの動きを表しています。
解説
次の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動かすような動的計画法と迷いましたが、重複組み合わせで一気に計算できた方がお得かな? と考え、今回の実装にしました。実際どうだったんでしょうか。