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]; } };