TopCoder SRM 427 Div1 Easy ShufflingMachine

問題

n枚のカードがある。
このカードを、次のような機械を使ってシャッフルする。

• 機械を一度通すと、i番目のカードがshuffle[i]番目に来るよう並び替えられる
• 1〜maxShuffleの整数を等確率で一つ選び、その回数だけデッキを機械に通す

その後、cardsReceived[]のカードをプレイヤーが受けとる。
いま、K枚のカードが欲しいとする。
最初のカードの並び順を自由に変えられるとき、目当てのカードを入手できる枚数の期待値を求めよ。

制約条件

n≦50
shuffle[i]は０0〜n-1の整数の順列
cardsReceivedの各要素は0〜n-1の重複しない整数
cardsReceivedの要素はK以上

方針

初期状態でi番目にあるカードが、最後に配られる確率はそれぞれ求まる。
確率が高い順に貪欲にK枚のカードをとれば、期待値が求まる。

ソースコード

class ShufflingMachine {
  public:
  double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K) {
    int n=shuffle.size(),m=cardsReceived.size();
    vector<double> e(n);
    vi ord;
    rep(i,n)ord.pb(i);
    rep(i,maxShuffles){
      vi nxt(n);
      rep(j,n)nxt[shuffle[j]]=ord[j];
      rep(j,m)e[nxt[cardsReceived[j]]]+=1.0/maxShuffles;
      ord=nxt;
    }
    sort(all(e));
    double ans=0;
    rep(i,K)ans+=e[n-i-1];
    return ans;
  }
};