仕事する日

適当に思いついた問題。

問題

営業日がN日ある。
R人のお客さんが営業日のうちどれかを1/Nの確率で選ぶ。
お客さんが1人以上いる場合は出社しなければならないが、いない場合は休みとなる。
出社しなければならない日数の期待値を求める。

N<=365
R<=200

考え方

P[i][j] := N日の中でi日をj人が予約する確率
を考える。P[1][1]=1は明らか。

今、P[i][j]がわかっているとき、
・人数が1人増える場合、P[i][j+1]の一部分として、P[i][j]、かつ、この人がN日からi日のどれかを選ぶ確率(i/N)、が含まれる
・人数が1人増えて、かつ、その人が誰もいない営業日を選ぶ場合、P[i+1][j+1]の一部分として、P[i][j]、かつ、この人がN日から(N-i)日のどれかを選ぶ確率(N-i/N)、が含まれる
ことがわかる。
あとは期待値を求めるため、Σi * P[i][R]を計算すればよい。