SRM-426 250pt: ShufflingMachine

keyword

期待値　Greedy　C++

問題概要

数列0,1,...,N-1(N<50)がある。これが1~S(<100)回(確率は一様)置換される。置換が終わった後、i_1, i_2, ..., i_p番目の数字が自分に割り振られる。最初に数列を並び替えることによって0,1,...,K-1が自分の手元に来るようにしたい。最善を尽くしたとき、いくつ得ることができるの期待値を求める問題。

解法

期待値の問題ではお馴染みの線形性を使う。置換をS回シミュレートして、数字jがi_1, i_2, … , i_p番目に出てくる回数をカウントする。後は出現頻度の高いものを上からK個とってくれば良い。

感想

期待値の問題は、線形性60%、DP(漸化式)30%、(連立)方程式5%、その他(2分探索とか)5%位な印象がある。問題文解読するのに時間をかけすぎた。

int cnts[110][110];
int as[110];

double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K) {
    double ret = 0.0;
    int i,j,N=SZ(shuffle);
    REP(i,110)REP(j,110) cnts[i][j] = 0;
    vector<int> cur(N), next(N);
    REP(i,N) cur[i] = i;
    FOR(i,1,maxShuffles+1){
        REP(j,N){
            next[shuffle[j]] = cur[j];
        }
        cur = next;
        REP(j,N){
            cnts[j][cur[j]]++;
        }
    }
    REP(i,N){
        as[i] = 0;
        REP(j,SZ(cardsReceived)){
            as[i] += cnts[cardsReceived[j]][i];
        }
    }
    REP(i,N)cout<<as[i]<<", ";cout<<endl;
    REP(i,K){
        int *p = max_element(as,as+N);
        ret += *p;
        *p = 0;
    }
    return ret/maxShuffles;
}