SRM426 Div2 500
問題
機械がカードの束のシャッフルする。このシャッフルは1〜maxShuffles回行われた後で各プレイヤーに配られる。あるチートプレイヤーがこのシャッフルの仕方が毎回同じだと突き止めた。そして、彼は最初のカードの並びを自由に変えられる。カードの中でK枚欲しいカードがあるとき、彼が受け取れる「欲しいカードの枚数の期待値」を答えよ。シャッフルの仕方はshuffle配列、配られる時彼が受け取ることができるカードのインデックスはcardsReceived配列で与えられる。
考え方
最初が{0,1,2}の並びのカードをshuffle={1,2,0}でシャッフルすると{1,2,0},{2,0,1},...となる。このシャッフルはmaxShuffles回まで行われるので、そのうちで受け取れるインデックスで一番回数の多いインデックスからK個分に欲しいカードを入れておけばよいことがわかる。そのとき、カードを受け取れる期待値は、欲しいカードを割り当てたインデックスの回数の合計をmaxShuffulesで割ることで得られる(一回当たりに得ることができるほしいカードの枚数)。
[例]Example 2 shuffle:{1,2,0,4,3} maxShuffles:7 cardsReceived:{0,3} K:2 実際にシャッフルさせて、最初のインデックスの動きを見てみると、(シャッフルがi回の場合) 最初:{0,1,2,3,4} 1回の場合:{1,2,0,4,3} 2回の場合:{2,0,1,3,4} 3回の場合:{0,1,2,4,3} 4回の場合:{1,2,0,3,4} 5回の場合:{2,0,1,4,3} 6回の場合:{0,1,2,3,4} 7回の場合:{1,2,0,4,3} となる。ここで受け取れるカードのインデックスは0番目と3番目のカードなので、 そのインデックスは、 1回の場合:1と4 2回の場合:2と3 3回の場合:0と4 4回の場合:1と3 5回の場合:2と4 6回の場合:0と3 7回の場合:1と4 である。それぞれの頻度は、 0->2回 1->3回 2->2回 3->3回 4->4回 である。K=2枚欲しいカードがあるので、回数が多いインデックスの場所に そのカードを割り当てればよく、それは最初のカードの{4番目と3番目}また は{4番目と1番目}に置けばいい。 そして、7パターンで7枚受け取る事ができるので、彼が受け取ることができる カードの期待値は7/7=1.0枚となる。