SRM478 Div2 Hard(1000) RandomAppleEasy

RandomAppleEasy

定義通りに計算しようとしたときに分母に出てくる数字（例１ならば2,3,5）は1000以下。分母の数字ごとに分子の数字を動的計画法で求める。i-1個目までの箱を考えたときに、分母jの項がn個で分子の合計がsならば、i個目の箱を加えることで、分母j+red[i]+green[i]の項が得られる。その個数はnで、分子の合計はs+n*red[i]。

#include <vector>
#include <cmath>

using namespace std;

class RandomAppleEasy
{
public:
    double theRed( vector <int> red, vector <int> green );
};

double RandomAppleEasy::theRed( vector <int> red, vector <int> green )
{
    int n = (int)red.size();

    vector<long long> sum(20*n+1);  sum[0] = 0;
    vector<long long> num(20*n+1);  num[0] = 1;

    for ( int i=0; i<n; i++ )
        for ( int j=20*n; j>=0; j-- )
            if ( num[j] > 0 )
                sum[j+red[i]+green[i]] += sum[j] + red[i]*num[j],
                num[j+red[i]+green[i]] += num[j];

    double p = 0;
    for ( int i=1; i<=20*n; i++ )
        p += (double)sum[i] / i;
    return p / ( pow(2.,n) - 1 );
}