リンク : https://csacademy.com/contest/archive/task/ball-sampling/ 問題概要 N色のボールがあり、箱にそれぞれA_i個入っている。同様に確からしいとき、すべての色のボールを一回以上取り出す期待値を求めよ。 解説 いわゆる、コンプリート問題と言われ…

リンク : https://csacademy.com/contest/archive/task/amusement-park/statement/ 問題概要 N*Mの行列Aが与えられる。このA[i][j]は座標(i,j)からA[i][j]の確率で座標(i,j+1)に進み、それ以外は座標(i+1,j+1)に進む。このとき、iがNになるときの移動回数の…

リンク : https://csacademy.com/contest/archive/task/expected-merge/statement/ 問題概要 マージソートのアルゴリズムと同様の関数を考えた時に、数列を半分にすることを繰り返す。奇数長の場合、区切られる場所は一意に定まらない。そこで、一様にランダ…