私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ディビジョン・ナイン」問題（CodeIQ）を参照してください。
1 から 4 の数字を使って n 桁の整数を作ります。このとき、9 の倍数となるものを考えましょう。
例えば n = 3 であれば、234、333、441、などが 9 の倍数です。必ずしも 1 から 4 の全ての数字を使う必要はありません。
1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。
例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。
標準入力から、自然数 n（1 ≦ n ≦ 20）が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。
Rubyで解答しています。
#!/usr/bin/ruby
$pattern = []
def perm(n)
if n == 0 then return 1 end
return (1..n).reduce(1, :*)
end
def calcPatternNum(arr)
cnt = Array.new(5, 0)
for a in arr
cnt[a] += 1
end
mx = cnt.max
if mx == arr.length then
return 1
else
return (perm(arr.length) / (perm(cnt[1]) * perm(cnt[2]) * perm(cnt[3]) * perm(cnt[4])))
end
end
def getResult()
n = 9
ret = 0
while n < $pattern.length
for l in $pattern[n]
ret += calcPatternNum(l)
end
n += 9
end
return ret
end
def makeNums(n, m)
result = nil
if m == 1 then
result = [[], [[1]], [[2]], [[3]], [[4]]]
else
result = Array.new(4*m+1){ Array.new }
for a in $pattern
for b in a
s = b.reduce(:+)
for i in 1..b[b.length - 1]
c = b.dup
result[s + i].push(c.push(i))
end
end
end
end
$pattern = result
if m < n then makeNums(n, m+1)
else return
end
end
while line = gets
line.strip!
if line.empty? then
next
end
makeNums(line.to_i, 1)
p getResult()
end
これは非常に難しかったです。同時期に★★★★の問題が出題されていましたが、私の感想としてはこちらの方がはるかに難しいと思いました。
9の倍数の性質である、各桁の数の合計が9の倍数である場合、9で割り切れる（＝9の倍数である）ことを利用します。n桁の数で9で割り切れるものは1〜4を合計n個組み合わせて数を作った時に選んだn個の数の合計が9の倍数になっているものです。
これは単純ですが20桁もの数でこれを数えるのは困難ですので、何らかの工夫が必要です。
ここでポイントになるのが選んだ数の順番は合計値に影響しないということです。例えば3桁で9になる1と4で作られた数には144、414、441がありますがこれらは4を2個と1を1個使った数です。逆に4を2個と1を1個使って3桁の数が何通り作れるかは同じものを含む順列で計算できます。
このことからn桁の数のうち1〜4の組み合わせが9の倍数になるものの数がわかれば答えば求められます。
合計値がXになる1〜4の組み合わせを作る関数です。
引数nは目的の桁数、mは現在何桁目を処理しているかを示すカウンタです。
結果はグローバル変数$patternに保持します。
| 合計 | 組み合わせ |
|---|---|
| 0 | なし |
| 1 | なし |
| 2 | (1,1) |
| 3 | (1,2) |
| 4 | (1,3),(2,2) |
| 5 | (1,4),(2,3) |
| 6 | (2,4),(3,3) |
| 7 | (3,4) |
| 8 | (4,4) |
| 合計 | 組み合わせ |
|---|---|
| 0 | なし |
| 1 | なし |
| 2 | なし |
| 3 | (1,1,1) |
| 4 | (1,1,2) |
| 5 | (1,1,3),(1,2,2) |
| 6 | (1,1,4),(1,2,3),(2,2,2) |
| 7 | (1,2,4),(1,3,3),(2,2,3) |
| 8 | (1,3,4),(2,2,4),(2,3,3) |
| 9 | (1,4,4),(2,3,4),(3,3,3) |
| 10 | (2,4,4),(3,3,4) |
| 11 | (3,4,4) |
| 12 | (4,4,4) |
答えの組み合わせ数を計算します。
ここで$patternの添え字が各桁の値の合計になっているのが効いてきて、添え字が9の倍数である要素を計算すれば9の倍数だけを数えることができます。$patternの要素は合計が要素番号になる1〜4の組み合わせなので、この組み合わせから何通りの値が作れるかを計算しなければなりません。例えば3桁で合計9になる組み合わせには(1,4,4)、(2,3,4)、(3,3,3)がありますが、これらを使って何通りの数が作れるかを計算しなければなりません。
getResult()ではcalcPatternNum()で(1,4,4)、(2,3,4)、(3,3,3)それぞれでできる組み合わせ数を計算し、それを足し合わせて答えにしています。
この関数は同じものを含む順列を計算します。この中で使っているperm()は順列を計算する関数です。例えば(1,4,4)で作れる3けたの数は144、414、441ですがこれは3!/(1!*0!*0!*2!)です。分子の3!は桁数、分母は1の数、2の数、3の数、4の数それぞれの階乗を掛け合わせたものです。
この関数では単純に12〜14行目で1〜4それぞれの数を数え、前述の計算をしています。17行目の条件は全部同じ数(3,3,3など)で構成される場合、1パターンしかないのは明らかなのでその分の計算量を減らすために入れています。
やたらと難しかったというのが感想です。解説では最終的にうまくいった方法だけを説明していますが、これにたどり着くまで相当の方法を検討しました。数え上げる時に5以上の数が現れた時に効率よく跳ばす方法（わからない）、格けたの数で1〜4だけが現れるパターン（ありそうだがわからない）、自然数分割でやる（例えば各桁の合計が72だったら72を1〜4以下の数だけで、N個に順番を考慮して分割できれば数を数えられます）、などです。
ちなみに2016/4/1 13:00現在で同時期に公開された問題の挑戦者数はこれが187人、「アイテム類似度のレコメンド」が77人、「世界は歪んでいる。それでも君は歩む。」が63人ですが、私にはこれが一番難しいです。しかし、挑戦者数からすると競技プログラミングの能力のある人にとってはこの問題の方が簡単なのでしょうか？