SRM 286 DIV1 Easy - ExtraBall (復習×○)

January 27, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=5891&rd=8083

・ビンゴゲームを行う。
・最初に紙には１～７５の数字が書いてあり、その数字がコールされるとその場所をくり抜くことができる。
・ビンゴゲームが終わったときに、与えられたパターンと同じところがくりぬかれたらそのパターンにおけるスコアを得ることができる。
・ここで、ゲームが終わった後にもう一つだけ数字をコールしてもらえることを考える。
・このとき、もう一つ数字をコールしてもらったときに得られる期待値を返す。

解き方

Exampleを読むことで問題のルールを把握することができるので、あとは実装するだけ。

くり抜かれたパターンが一致するかの関数を作り、くり抜かれていない差が一つかどうかを判定すればあとは簡単。

コード

class ExtraBall {

public:

bool match(string a,string b){
int dif=0;
FORE(i,0,a.size())if(a[i]=='.'&&b[i]=='X')dif++;
return dif==1;
}

double expectedPayout(vector<int> card, vector<int> balls, vector<string> patterns, vector<int> prizes) {
string org="";
FORE(i,0,card.size())org+='.';
FORE(i,0,card.size())FORE(j,0,balls.size())if(card[i]==balls[j])org[i]='X';

int cost=0;
FORE(i,0,patterns.size())if(match(org,patterns[i]))cost+=prizes[i];

return (double)cost/(double)(75-balls.size());
}

};

確率