王女様のジェムストリング問題

python コード

class cnc(object):
    def __init__(self):
        self.cdict = {}

    def ncount(self, alist):
        tmp = [a for a in alist]
        tmp.sort()
        if tuple(tmp) in self.cdict:
            return self.cdict[tuple(tmp)]    
        blist = []
        if len(alist) > 1:
            for i in range(len(alist)):
                if alist[i] > 1:
                    blist.append(alist[:i] + [alist[i]-1] + alist[i+1:])
                else:
                    blist.append(alist[:i] + alist[i+1:])
            res = sum([self.ncount(b) for b in blist]) + 1
            self.cdict[tuple(tmp)]=res
            return res
        else:
            self.cdict[tuple(tmp)]=alist[0] + 1
            return alist[0] + 1

def nc(alist):
	""" ある宝石セットで作れる組み合わせの数 """
    t = cnc()
    return t.ncount(alist) - 1

# 数え上げの方は力技で積み上げてしまった	
print ( nc([4,1,4,2,1,3])
    + nc([1,3,1,4,2,1,3])
    + nc([1,4,4,2,1,3])
    + nc([1,4,1,3,2,1,3])
    + nc([3,1,4,1,1,3])
    + nc([4,4,1,1,3])
    + nc([4,1,3,1,1,3])
    + nc([4,1,4,1,3])
    + nc([4,1,4,1,3])
    + nc([3,1,4,1,1,2])
    + nc([3,4,1,1,2])
    + nc([3,3,1,1,2])
    + nc([4,2,1,1,2])
    + nc([4,3,2])
    + nc([2,3,1,2])
    + nc([3,2,1,2])
    )