2020 Humbleool Cup Prelims

　オンサイトか何か（？）の予選で、Div.1、Div.2混合回。
　Div.2の難易度で、全完しないとまずいセットだったのに、Hardをミスして落とす。
　それでも、緑から青に戻ったけれど、これは出なくても良かったかなぁ、という気持ちになりました。

　なお、MedはPython最速だったらしく公式ページに自分の実装が載っています。

CardDrawPoints

　カードの枚数の制約が少ないことからも分かる通り、bit DPをする問題。

　どのカードを使った/使ってないか、の期待値をbit DPで計算すればOK。

　floatで割り算して誤差が大丈夫か不安だったけれど、それも問題なかった。

　コンテスト中は、残り枚数が0枚のときに、0除算して落としてしまった。ちゃんと気を付けないと！

　一応、システムテストを通ったコードを載せておきます。

class CardDrawPoints():
    def expectedScore(self, count):
        LEN=len(count)
        if max(count)==0 or len(count)==1:
            return 0

        LIST=[-1]*(1<<LEN)
        def calc(A):
            if LIST[A]!=-1:
                return LIST[A]
            
            rest=[0]*LEN
            NOW=0

            for i in range(LEN):
                rest[i]=count[i]
                if A & (1<<i)!=0 and count[i]>0:
                    NOW+=i
                    rest[i]-=1

            SUM=sum(rest)

            if SUM==0:
                return NOW

            ANS=float(0)

            for i in range(LEN):
                if A & (1<<i)!=0:
                    continue
                else:
                    ANS+=float(calc(A|(1<<i)))*rest[i]/SUM

            if NOW>ANS:
                LIST[A]=NOW
                return NOW
            else:
                LIST[A]=ANS
                return ANS

        for i in range((1<<LEN)-1,-1,-1):
            calc(i)

        return LIST[0]