SRM 626 練習
そろそろICPCなので競技に復帰してみたり。 AOJとかちょろっとやって、明日はTopCoderだったりするので前回のSRMのeasyを解いてみた
157.19 / 250 pts まぁまぁかな。割とさくっと解けた気分でいたけど大分かかってる気もする。 同じチームの人に勝っていたから良いとしよう。 どうやったかというと、スコア全ての確率を計算してから適当にやる。
O(aba + cdc)くらい?
// 157.19 / 250 pts. const double not_calc = -1; double prob(int k,int want,vector<vector<double>>& memo,const int n){ if(want < 0) return 0; if(k == 0){ return want == 0; } if(memo[k][want] != not_calc){ return memo[k][want]; } double ret = 0; for(int i=1;i<=n;i++){ ret += prob(k-1,want-i,memo,n); } ret /= n; return memo[k][want] = ret; } class FixedDiceGameDiv1{ public: double getExpectation(int a, int b, int c, int d){ if(a*b <= c) return -1; vector<double> alice(a*b+1); { vector<vector<double>> memo(a+1,vector<double>(a*b+1,not_calc)); for(int i=0;i<alice.size();i++){ alice[i] = prob(a,i,memo,b); } } vector<double> bob(c*d+1); { vector<vector<double>> memo(c+1,vector<double>(c*d+1,not_calc)); for(int i=0;i<bob.size();i++){ bob[i] = prob(c,i,memo,d); } } vector<double> sum_bob(bob.size()+1); for(int i=1;i<sum_bob.size();i++){ sum_bob[i] = sum_bob[i-1] + bob[i-1]; } while(sum_bob.size() <= alice.size()){ sum_bob.push_back(1); } double ret = 0; double prob_of_win = 0; for(int a=1;a<alice.size();a++){ prob_of_win += alice[a] * (sum_bob[a]); ret += a*alice[a]*sum_bob[a]; } ret /= prob_of_win; return ret; } };