WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM568 Div2 Hard "ShuffleSort"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11156

N枚のカードがあり、それぞれのカードに数字が書かれている。
複数のカードに同じ数字が書かれている場合もあり、そのようなカードは見分けがつかない。

このデッキ(N枚のカード)をソートしたいと考えている。
正確に言えば、カードをテーブルの上に非減少になるように一列に並べたい。
これを達成するために、次のようなプロセスを踏む(最初はステップ1を行う)

step1 デッキをシャッフルする。(結果は完全にランダムになると考えてよい)
step2 デッキのカードで最も小さい数字をXとする。デッキの一番上のカードをめくり、
   それがXでなければstep1に戻る。Xであれば、それをテーブルの列に並べる。
   この時、デッキがなくなれば作業は終わりとなり、
   まだ残っていればstep2を繰り返す。(デッキをシャッフルせずに!)

デッキのカードの数字が与えられるので、作業が終わるまでに何回シャッフルするか、
その期待値を返せ。

制約

1 <= N <= 50
1 <= カードに書かれている数字 <= 50



う~ん・・・

解けるまでにSRM568 Editorialに頼りっきりの問題だった。
確率・期待値はホント無理です。自分の中で得体が知れないものとなっております。

一般的にはDiv2 Hardにしては簡単で、
Mediumよりも簡単だったとの声も上がっているとかいないとか・・


例えばデッキが{ 1, 2, 3 }だとすると、

1/6の確率で{ 1, 2, 3 }となって1回で終わり
1/6の確率で{ 1, 3, 2 }となって状態が{ 2, 3 }へと移行する
4/6の確率で{ 2, 1, 3 }などとなって状態変わらず。

なんですが、
状態がループして無限になっちゃうじゃん!どーすんのよ!
って感じでした。自分は・・・

で、カードの残り枚数をnとして、シャッフル期待値をf(n)とすると、
{ 1, 2, 3 }でのシャッフル期待値f(3)は
f(3) = 4/6 * (f(3) + 1) + 1/6 * (f(2) + 1 ) + 0/6 * (f(1) + 1 ) + 1/6 * (f(0) + 1)
という式が立てられて、ここからf(3)を求めることが可能なんですって。


EditorialのA simpler recurrence relationの項目が
どうしても理解できず。
要復習ですな


ソースコード

class ShuffleSort {
public:

    // デッキのインデックスsから値vのカードが何枚あるかを返す
    int num( vector<int>& cards, int s, int v ){
        int res = 0;
        int n = cards.size();
        int i = s;
        while( i < n && cards[i++] == v ) res++;
        return res;
    }

    double shuffle(vector <int> cards){
        int n = cards.size();
        sort( cards.begin(), cards.end() );

        double f[55]; // f[i] 残りi枚のときの期待値
        f[0] = 0;     // 0枚のときのシャッフル期待値は0回
        // f(i)を求める
        for( int i = 1; i <= n; i++ ){

            // f(i)時のp(0)を求める
            int m =  num( cards, n-i, cards[n-i] );
            double p0 = 1 - (double)m / i;

            double e = p0; // 期待値
            double r = 1.0 - p0; // 残り期待値
            // p(j) * (f(i-j) + 1)を求め、足していく
            for( int j = 1; j < i; j++ ){
                double m = num( cards, n-i+j, cards[n-i+j] );
                double p = r * (1 - (double)m / (i - j));
                r -= p;
                e += p * ( f[i-j] + 1 );
            }
            e += r;
            f[i] = e / (1 - p0);
        }

        return f[n];
    }
};