AOJ 数列のコンビネーションプログラム

「Combination of Number Sequences」を直訳したら、数列のコンビネーションになりました。

■問題
Combination of Number Sequences

■問題文の解釈
入力データが

3 10

のとき、k1 + 2×k2 + 3×k3 = 10を満たすk1,k2,k3は以下の8通りある。

3 2 1
4 0 2
1 0 3
8 1 0
6 2 0
4 3 0
2 4 0
7 0 1

以上を踏まえて、プログラムを書きます。

・・・・・
・・・・・

けっこう難しいぞ。 🙁

私の今までのくだらない人生から判断すると、再起を使うような気がします。

■最初のプログラム
試行錯誤の末、こんなプログラムが完成しました。

# 数列のコンビネーションプログラム
import sys

def get_sequence(s, n, k, ks):
    # s : 合計
    # n : n個の数字
    # k : k番目の数字を処理中(1〜10)
    # ks: 使用していない数字

    if k == n:

        if s % k == 0:
            if s // k in ks:
                #print('s:{} k:{} n:{} ks:'.format(s, k, n), end='')
                #print(ks)
                return 1
            else:
                return 0
        else:
            return 0

    cnt = 0
    for i in ks:
        s_copy = s
        s_copy -= i * k
        if s_copy < 0:
            break
        
        k_copy = k
        k_copy += 1
        if k_copy > n:
            break
        
        ks_copy = ks[:]
        ks_copy.remove(i)
        #print('i:', i)
        cnt += get_sequence(s_copy, n, k_copy, ks_copy)

    return cnt
        
def main():
    while True:
        line = sys.stdin.readline().strip()
        if line is None or line == '':
            break

        data = line.split(' ')
        n = int(data[0])
        s = int(data[1])
        cnt = get_sequence(s, n, 1, list(range(10)))
        print(cnt)

if __name__ == '__main__':
    main()

こいつを提出すると、しばらく待った挙句、時間切れとなってしまいました。
どうやら、私のアルゴリズムでは時間計算量が大きすぎるようです。

改善しなければなりません。

■つぶやき
数式になんらかの数学的特徴があるのかな。

Pythonプログラミング物語 © 2016 Frontier Theme