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;
    }
};