ホームに戻る
TopCoder の傾向と対策６（Ｃ＋＋編：確率、期待値）
０、はじめに
確率の問題はたまにでます。
期待値の問題は確率の問題より良くでます。
期待値の問題だというだけで解けないのはもったいないです。
いろいろなパターンがあるのでいくつかやってみます。
ポイントは 式 を正確に書いてみることだと思っています。
１、確率
もし総当りが可能であれば総当りで数えればよい。
このとき (該当する回数)/(すべての回数) で答えがでる。
総当りができないときに確率の計算の考え方が必要になる。
サイコロの場合出る目は 1,2,3,4,5,6 の６通り。
このとき３の目がでる確率は 1/6 である。
３か４の目のどちらかがでる確率は 1/3 である。
３の目も４の目もでない確率は 2/3 である。
サイコロが２個の場合共に６が出る確率は 1/36 である。
３か４がでる場合の例は 1/6 + 1/6 をしている。
３も４もでない場合の例は 1 - 1/3 をしている。
共に６がでる場合の例は 1/6 * 1/6 をしている。
確率の和か差か積をすることで複雑な確率も計算できる。
例えば次の問題は確率の和と積を組み込んでＤＰで解いている。
問題
各６面の数字が１以上１０以下のサイコロがある。
例えば、１、１、２、３、５、７であるとする。
このサイコロを１０個同時に振ったときに目の合計が
ちょうど５０になる確率を求めよ。
double dp[111];
int d[6] = {1, 1, 2, 3, 5, 7};
dp[0] = 1.0; // サイコロを０個振ったとき合計が０になる確率は 1.0
for(int i = 1; i <= 100; i++){
dp[i] = 0.0;
}
for(int i = 0; i < 10; i++){
for(int j = 100; j >= 0; j--){
for(int r = 0; r < 6; r++){
dp[j + d[r]] += dp[j] / 6.0; // ここで積と和をしている
}
dp[j] = 0.0;
}
}
return dp[50];
浮動小数の精度を気にするかもしれないが、
解答を浮動小数で返す場合には精度が大きくそれることはあまり無い。
精度を気にするべきなのは浮動小数の比較を行う場合である。
２、複雑な確率
問題
最大５０個の地点がある。
グラフで移動できるかどうかあらわされる。
graph[i][j] == '1' であれば i から j へ移動できる。
また、ひとつの地点は勝率と負率を持つ。
（勝率＋負率）は必ずしも１００％であるとは限らない。
勝ち負け以外の場合には次の移動が発生する。
Start 地点からスタートする。
地点を１つ移動し、移動した地点で勝ち負け判定をする。
（注意：自分自身に移動することもできる。）
勝ちか負けのいずれかが確定すれば終了する。
これを繰り返す。
得ることのできる最大の勝率を求めよ。
考え方
勝率の最も高い地点にとどまれば良い、という考えがすぐに浮かぶ。
ただし、そこにたどり着くことができるか？という問題がある。
０地点から１地点、１地点から２地点へ移動できるとき。
２地点の勝率がベストだが、１地点の負率が高いとき、
１地点を通るリスクをおかして２地点へ行くかどうかは迷う。
式を立ててどのようになるかを考えてみる。
i 地点と隣り合う j 地点について、
p[i] = max(p[i], 勝率[j]+(100-(勝率[j]+負率[j]))*p[j])
とできる。
隣り合う j 地点から i 地点にたどり着くことによって、
現在の i 地点の最大の勝率を更新できれば更新するやり方になる。
Start 地点からどのように探索するかを考え更新すれば良い。
しかし、もっと簡単なやり方がある。
式の更新を単純に地点の数だけ繰り返す。
この更新である地点から地点数だけ移動した場合の結果がわかる。
下の例では十分量の 100 回の移動をしている。
実際に必要量は地点の数で良い。
double p[50];
for(int i = 0; i < graph.size(); i++){
p[i] = 1. * winprob[i] / (winprob[i]+looseprob[i]);
}
for(int i = 0; i < 100; i++){
for(int j = 0; j < graph.size(); j++){
for(int k = 0; k < graph.size(); k++){
if(graph[j][k] == '1'){
p[j] = max(p[j], 0.01*winprob[k]+0.01*(100.-(winprob[k]+looseprob[k]))*p[k]);
}
}
}
}
cout << p[Start] << endl;
３、期待値
もし総当りが可能であれば総当りで数えればよい。
このとき (該当する場合の総和)/(該当する回数) で答えがでる。
言い換えれば期待値は平均値と言っても良い。
例えばサイコロを１回振るときに出る目の期待値は、
(1+2+3+4+5+6)/6 = 3.5
よって、3.5 が答えになる。
期待値には次の法則が成り立つ。
事象Ｘの期待値を E(X) とするとき、
E(aX) = a*E(X)
E(X+Y) = E(X)+E(Y)
例えば、サイコロで出る目の期待値は 3.5 であった。
これは (1+2+3+4+5+6)/6 で計算できる。
このとき (出た目の数)*10 を点数とする場合、
点数の期待値は 3.5*10=35 としても良い。
これは E(aX) = a*E(X) であると言える。
また、サイコロを２個振って出た目の数の期待値は、
3.5+3.5=7 なので、E(X+Y) = E(X)+E(Y) であるといえる。
また X,Y が独立のとき E(XY)=E(X)*E(Y) ともいえる。
問題
ある英小文字からなる文字列が与えられる。
例えば "aaba" という文字列が与えられたとする。
このとき何文字か抜き出して回文であるものを調べる。
すると "a"、"a"、"b"、"a"、"aa"、"aba" の６つが回文である。
"?" は等確率で a から z のいずれかの文字を意味するとする。
"???a?bb?a?bx?" からいくつの回文を抜き出せるか？
期待値を求めよ。
解説
これまでの期待値の解説でこの問題は解ける。
簡単のため "??a?" という文字列を考える。
まず "?" はどの文字でも１つの回文になると考えられる。
"a"は言うまでもなく１つの回文と言える。
"??" は ? に同じ文字が入れば回文であるので 1.0*1/26 つの回文。
"?a"、"a?" は ? が a であれば良いので 1.0*1/26 つの回文。
"??a" は最初の ? が a であれば良いので 1.0*1/26 つの回文。
"?a?" は ? が同じであれば良いので 1.0*1/26 つの回文。
"??a?" は２つめの ? が a で両端が同じであれば良い。
よって、1.0*1/(26*26) つの回文になる。
ゆえに、
期待値 E = E("?")+E("?")+E("a")+E("?")+E("??")+E("?a")+E("a?")
+E("??a")+E("?a?")+E("??a?")
を計算すれば良い。
string s = "???a?bb?a?bx?";
double ans = (double)s.sz;
for(int i = 0; i < s.sz; i++){
for(int j = 0; j < 2; j++){
int a = i-j;
int b = i+1;
double e = 1.0;
while(0 <= a && b < s.sz){
if(s[a] == '?' || s[b] == '?'){
e /= 26.0;
ans += e;
}
else if(s[a] == s[b]){
ans += e;
}
else{
break;
}
a--;
b++;
}
}
}
cout << ans << endl;
答えは 14.8258531704123779348947 となる。
問題
A君とB君がサイコロで勝負をする。
A君は1からNの目がでるサイコロを持っており、
B君は1からMの目がでるサイコロを持っている。
サイコロの目が大きい方が勝ちであるとき、
A君がB君に勝負で勝ったことはすでにわかっている。
このときA君が出した目の期待値は？
解説
A君が勝つ場合の期待値を求めるだけではいけない。
A君が勝つ場合の期待値をA君が勝つ確率で割る。
double a = 0.0;
double b = 0.0;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
if(j < i){
a += 1. * i / N / M;
b += 1. / N / M;
}
}
}
cout << a/b << endl;
４、回数の期待値
回数の期待値を求める場合に次の式を用いる。
E(X) = p1*E(X1) + p2*E(X2) + ・・・ + 1
X になるための X1 や X2 という状態があり、
X1 から X 、 X2 から X へ移行する確率がそれぞれ p1 、 p2 であるとき、
X1 、X2 に至るまでの期待値から X の期待値を求めることができる。
回数の期待値は良くでるのでこの式は覚えておきたい。
問題
１から１０の数字が書かれたカードが各１枚、全１０枚ある。
ランダムでカードを２枚引くと「３」と「８」がでた。
合計を２０以上にするためにはあと何枚引く必要があるか？
引く枚数の期待値を求めよ。
解説
例えば、E(X) = p1*E(A)+p2*E(B)+1 であった場合、
E(A) と E(B) が必要になる。
このとき E(A) も E(B) も再帰を使って E(X) と同じように計算できる。
合計の数が２０以上なら引く枚数の期待値は 0 であるため、
再帰の終点を合計が 20 以上であれば 0 を返す、にすれば良い。
問題は E(A) を計算する際に E(X) が必要になるとループしてしまう。
この設問に関してはループしないので再帰で書いて解けるが、
ループしてしまうときにはこの解法では解けない。
double f(int n, int d[]){
if(n >= 20){
return 0.0;
}
int total = 0;
for(int i = 1; i < 11; i++){
total += d[i];
}
double ret = 0.0;
for(int i = 1; i < 11; i++){
if(d[i] == 0){
double p = 1.0 / total;
d[i] = 1;
ret += p * f(n + i, d);
d[i] = 0;
}
}
return ret + 1.0;
}
int main(){
int d[11];
for(int i = 1; i < 11; i++){
d[i] = 0;
}
d[3] = 1;
d[8] = 1;
printf("%f\n", f(3 + 8, d));
return 0;
}
５、最善の戦略をとるときの期待値
期待値は確率によって変化する値の平均である。
しかし、最善の戦略をとる場合の期待値を求める場合がある。
これは「最善の戦略」と「確率」が混在するため、
考え方に混乱が生じる原因になる。
最善の戦略を使った場合の期待値を求める場合には、
後ろから前にさかのぼる方法を使い、
さかのぼるときに結果の良いほうを選択していけば良い。
問題
０地点からスタートしＸ地点の敵（最大５０匹）を倒す。
体力は最初Ｍあり１地点ぶん移動すると１減る。
敵に遭遇すると戦うか戦わないかを選択できる。
敵に確率Ｐ％で勝つと体力がＧだけ回復する（Ｍは超えない）。
(100-Ｐ)％で戦いに負けると体力が０になり終了する。
戦わない場合は体力に変動は無く続けて進める。
最善の方法で最高で何地点まで進めるか？期待値を求めよ。
解説
この問題も再帰で解ける。
再帰の途中で最適な結果を選択していく。
最適な結果を選択する性質上、前から解くことはできない。
double dp[55][100001];
struct Data{
int a;
int b;
int c;
Data(int a, int b, int c):a(a), b(b), c(c){};
bool operator <(const Data &p) const {
return (a < p.a);
}
};
Data md(int a, int b, int c){
return (Data(a, b, c));
}
int M;
vector<Data> v;
double f(int n, int day,int m){
if(dp[n][m] != 0){
return dp[n][m];
}
if(n == (int)v.sz){
return m;
}
else{
int d = v[n].a-day;
if(d >= m)return m;
return dp[n][m] = max(d+f(n+1,v[n].a,m-d), 1.*d*(100-v[n].b)/100. + 1.*(f(n+1,v[n].a,min(M,m-d+v[n].c))+d)*v[n].b/100.);
}
}
for(int i = 0; i < day.sz; i++){
v.pb(md(day[i],win[i],gain[i]));
}
sort(v.begin(), v.end());
memset(dp,0,sizeof(dp));
cout << f(0,0,M) << endl;
６、結果が回転するときの期待値
E(0) を求めるために E(1) が必要であり、
E(1) を求めるために E(0) が必要である場合がある。
この場合は再帰を書くと無限ループする。
よって、連立方程式を書いて解く方法を考える。
ここで Gauss-Jordan 法を使う。
例題
n 個の一列のマスがある。
各マスから隣のマスには等確率で１つ移動できる。
start マスから goal マスに移動するための移動回数の期待値は？
マスが３つ、start が 0、goal が 2 のとき、
E(0) = E(1) + 1
E(1) = (1/2)*E(0) + (1/2)*E(2) + 1
E(2) = 0 // ゴールからゴールにたどり着くまでの期待値は 0
以上のような式が書ける。
これを Gauss-Jordan で用いる行列で表現する。
| 1 -1 0 ||E(0)| = |1|
| -1 2 -1 ||E(1)| = |2|
| 0 0 1 ||E(2)| = |0|
あとはこれを Gauss-Jordan の関数で処理するだけ。
式を立てて、行列に当てはめるまでが難しい。
#define N 50
double a[N][N], b[N], x[N];
void gj(int n){
int i, j, k;
double w, m, s;
for(k = 0; k < n-1; k++){
w = 1.0 / a[k][k];
for(i = k + 1; i < n; i++){
m = a[i][k] * w;
for(j = k + 1; j < n; j++){
a[i][j] -= m * a[k][j];
}
b[i] -= m * b[k];
}
}
x[n-1] = b[n-1] / a[n-1][n-1];
for(k = n-2; k >= 0; k--){
s = 0.0;
for(j = k + 1; j < n; j++){
s += a[k][j] * x[j];
}
x[k] = (b[k] - s) / a[k][k];
}
}
int start = 2;
int goal = 3;
int n = 6;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 0; i < n; i++){
if(i == goal){
a[i][i] = 1;
}
else{
int c = 0;
if(i-1 >= 0){
c++;
a[i][i-1] = -1;
}
if(i+1 < n){
c++;
a[i][i+1] = -1;
}
b[i] = a[i][i] = c;
}
}
gj(n);
cout << x[start] << endl;
７、期待値の線形性
期待値の線形性とはE(X+Y)=E(X)+E(Y)やE(aX)=aE(X)を満たす場合である。
全体の期待値を求めるのではなく個々の期待値を求めておいて後で足したり数倍することで全体の期待値が求まることがある。
例えば、次のような例がわかりやすい例である。
問題
Ｎ枚の表向きのコインがある。
ここからa[i]枚のコインをランダムに裏返す。
この操作を K 回行ったときコインの表の枚数の期待値は？
例えば、10枚のコインが表を向いている。
適当に3、10、2、5、9枚のコインを裏返す。
5回の操作が終わったときに表を向いているコインの数の期待値は？
解説
１枚のコインに注目する。
すると N 枚中 a[i] 枚裏返すので、
裏返る確率は a[i]/N であることがわかる。
コインが表である確率は、
表が表であり裏返らないか、裏であり裏返るとき。
これを更新していくと、
１枚のコインが最終的に表を向いている確率がわかる。
期待値はその確率のＮ倍である。
int N = 10;
int k = 5;
int a[k] = {3,10,2,5,9};
double ret = 1.0;
for(int i = 0; i < k; i++){
double q = (double)a[i] / N;
ret = ret * (1 - q) + (1 - ret) * q;
}
cout << ret*N << endl;
この解法だとKがたとえ1000000回でも解けてしまう。
期待値の線形性を使う問題は大きな回数でも解けるために解法を推測されやすい。
わざと回数を少なくして出題されることが多いように思う。
