TopCoder SRM 426 Div2 Med, Div1 Easy: ShufflingMachine

SRM練習会に参加。EasyMed提出ACで298.01pt。本番だと117位。はじめて自力でMedを通せた。

問題

カードをシャッフルして配るゲームがある。
シャッフルによる順番の変化は決まっており、あなたはそれを知っている。
またシャッフルの回数は1から最大回数のうちどれかがランダムに選ばれる。
さらに、あなたはシャッフル後にK枚のカードを受け取るが、受け取るカードの位置をすでに知っている。
あなたは欲しいカードがK枚あり、手に入る欲しいカードの枚数の期待値が最大になるようにはじめのカードの並びを設定できる。
期待値が最大になるように並び替えたときのその期待値を答えよ。

解法

各シャッフル回数ごとに自分が受け取る位置にくる初期位置を数えていく。
受け取る位置にくる回数が多い初期位置から順番にK個、その回数を足し合わせていく。
最後にこれをシャッフルの最大回数で割れば、手に入る欲しいカードの枚数の期待値の最大を得られる。
カードに被りはなく、シャッフルの回数ごとに手に入る欲しいカードの枚数は独立しているのでこれで答えが計算できる。

def stackDeck(self, shuffle, maxShuffles, cardsReceived, K):
    M = len(shuffle)
    shuffle = [list(shuffle) for i in xrange(maxShuffles)]
    
    for i in xrange(1, maxShuffles):
        shuffle[i] = [shuffle[i - 1][j] for j in shuffle[0]]
        
    hist = [0] * M
    for i in xrange(maxShuffles):
        for j in cardsReceived:
            hist[shuffle[i][j]] += 1
    print hist
    hist = sorted(hist, reverse = True)
    ans = 1.0 * sum(hist[:K]) / maxShuffles
    
    return ans