SRM 426 div1 easy:ShufflingMachine

SRM練習会に参加。easyとmed解けてしかもmedが結構早かったので良かったと思います。

問題

TopCoder Statistics - Problem Statement

解法

それぞれの場所に目的のカードを仕込んだ時i回動かしたらどこにカードが向かうかを記憶し,それぞれのシャッフル回数でカードを取り出すことができるかを確かめる。

取り出すことのできる確率が高いものから順に貪欲に目的のカードを仕込む場所を決定し,期待値を求める。

class ShufflingMachine {
public:
    double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K) {
        int M = shuffle.size();
        vector<int> rs(M);
        vector<double> p(M);
        for (int i = 0; i < M; i++) rs[shuffle[i]] = i;
        for (int i = 0; i < M; i++) {
            int pos = i;
            int get = 0;
            for (int j = 0; j < maxShuffles; j++) {
                pos = rs[pos];
                if (find(cardsReceived.begin(), cardsReceived.end(), pos) != cardsReceived.end()) get++;
            }
            p[i] = 1. * get / maxShuffles;
        }
        sort(p.rbegin(), p.rend());
        double ret = 0;
        for (int i = 0; i < K; i++) ret += p[i];
        return ret;
    }
};

問題文長いのはやめていただきたい(難易度的には220ptくらい取れて良さそうだが最初問題文が全く理解できなかったので160ptしか取れなかった)。
英語勉強したほうが良いんですかね…