王女様のジェムストリング問題
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]) )