SRM426 Div1 Easy ShufflingMachine

2015/06/21 (Sun) SRM 期待値

問題

問題文

(以降の文では変数名が問題で与えられている名前とかなり違っています．)

カードが一列に並んでいる．それを配列 $f$ にしたがって入れ替える(カード $i$ が $f[i]$ に移る)という操作が， $1$ 回から $t$ 回までの間のランダムな回数だけ行われる． あなたはほしいカードが $k$ 枚あり，シャッフル後のインデックスが配列 $cs$ に含まれるカードをもらえることがわかっている． もらえる枚数の数が最大化するように最初の配置を自由に設定できるとき，もらえる枚数の期待値を答えよ．

方針

毎回のシャッフル後について，各カード $i$ が $cs$ に含まれる位置にある確率を求め，$dp[i]$ に足していく． 最後にこれを降順ソートして前から $k$ 個の要素を足して $t$ で割ったものが答え．

実装

class ShufflingMachine {
public:
    vector<double> dp;
    double stackDeck(vector <int> f, int t, vector <int> cs, int k) {
        int n = f.size();
        dp.assign(n,0);
        vvi ord(t+1,vi(n));
        rep(i,n) ord[0][i] = i;
        rep(i,t) rep(j,n) ord[i+1][f[j]] = ord[i][j];

        rec(1,n,t,cs,ord);
        sort(dp.rbegin(), dp.rend());
        return accumulate(dp.begin(),dp.begin()+k,0.0) / t;
    }

    double rec(int k, int n, int t, vi & cs, vvi & ord){
        if(k > t) return 0;
        rep(i,n){
            for(int c:cs) if(ord[k][i]==c) dp[i]++;
        }
        return rec(k+1,n,t,cs,ord);
    }
};