TopCoder Single Round Match 798

　Easyをパッと思いつけなかった上、Pythonじゃ通らない制約のためC++へ書き直したためタイムロス。そのためMedが解きおわらず。

コンテスト後のツイート

Div1 Easy SuperSubset

　部分和問題なのでDPしようとは思えて、あとは上手く辻褄合わせれば良い。

　具体的には、初期値をDP[0]=pow(2,len(A))にして、一つ使ったら自由度が半分になるので、

・DP[i+a]+=DP[i]/2

　みたいに遷移させれば良い。

Div1 Med ExpectedValue

　コーディングフェーズ終了三分後に解き終わった。

　A[i]=jのとき、iとjを結ぶとすると、N個の要素が何個のグループに分けられるかで答えは決まる。

　愚直解を書いてグループの個数を調べると、

・DP[i][j]=(DP[i-1][j]*(i-1)+DP[i-2][j-1]*(i-1)

　のように推測でき、これで答えを求めたら通った。

　以下、Practiceでシステムテストを通ったコード。

mod=10**9+7
DP=[[0],[0],[0,1],[0,2],[0,6,3]]
 
for i in range(5,1501):
    X=[0]*(i//2+1)
    for j in range(1,i//2+1):
        if i%2==0 and j==i//2:
            X[j]=(DP[-2][j-1]*(i-1))%mod
        else:
            X[j]=(DP[-1][j]*(i-1)+DP[-2][j-1]*(i-1))%mod
            
    DP.append(X)
        
 
class ExpectedValue():
    def solve(self, N):
        S=sum(DP[N])
        ANS=0
        for i in range(len(DP[N])):
            ANS=ANS+i*DP[N][i]
            ANS%=mod
        return (S*N-ANS)*pow(S,mod-2,mod)%mod