ディビジョン・ナイン

問題概要

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) の値を出力するプログラムを書いてください。

解法

n 桁で表すことができる値 i を書き出していけば以下のようにパスカルの三角形みたいになる。
f:id:Matchald:20160319174858p:plain

n 桁で値 m を表す個数は、(1桁目を1として(n-1)桁で(m-1)を表す個数)+(1桁目を2として(n-1)桁で(m-2)を表す個数)+・・・(1桁目を4として(n-1)桁で(m-4)を表す個数)であるので、
value[桁][値] = value[桁 - 1][値 - 1] + value[桁 - 1][値 - 2] + value[桁 - 1][値 - 3] + value[桁 - 1][値 - 4]
である。

Python3によるコード

n = int(input())
l = [[0 for i in range(4*n + 1)] for j in range(n + 1)]

# l[桁数][値]
l[1][1] = l[1][2] = l[1][3] = l[1][4] = 1

count = 0
for i in range(2, 4*n+1):
    for j in range(2, n + 1):
        l[j][i] = sum(l[j - 1][i - 4 if i - 4 >= 0 else 0:i])
        if i % 9 == 0 and j == n:
            count += l[j][i]

print(count)


このコードはnが大きくなるとメモリ効率が悪い。

私のコードでは、ある値 i から i -4 までの5つの値を n 桁ぶん覚えていればよいので、最低限必要な配列は n \times 5 でよい。