SRM513 Div1 Medium(500) PerfectMemory

PerfectMemory

残っているカード枚数と、そのうち一度もめくっていないカードの枚数ごとに、最小手数の期待値を覚えておいて、動的計画法。

一度もめくっていないカードを最初にめくるのが最善で、１枚目が既にめくったシンボルの場合、２枚目はそのシンボルをめくれば良い。１枚目が既にめくったシンボルではない場合、２枚目は、１枚目と同じ、１枚目以外の既にめくったシンボルと同じ、２枚目も初めて見るシンボル、というパターンがある。

２枚目がに１枚目以外の既にめくったシンボルと同じ場合、その場でもう一度２枚目をめくって取るとすると、一度めくったカードの枚数は残っているカードの半分以下で、一度めくったカードのシンボルは全て異なるとすることができる。

#include <vector>
using namespace std;

class PerfectMemory{public:
double getExpectation( int N, int M )
{
    int S = N*M;

    //  [残っているカード][一度もめくっていないカード]
    vector<vector<double> > T( S+1, vector<double>(S+1) );

    T[0][0] = 0;

    for ( int i=2; i<=S; i+=2 )
    for ( int j=i/2; j<=i; j++ )
    {
        T[i][j] = 0;

        double p = (double)(i-j)/j;
        //  １枚目がすでにめくったカードと同じシンボル
        T[i][j] += p * (T[i-2][j-1]+1);
        //  １枚目と２枚目が同じシンボル
        if ( j>=2 )
            T[i][j] += (1-p) * (double)1/(j-1) * (T[i-2][j-2]+1);
        //  ２枚目がすでにめくったカードと同じシンボル
        if ( j>=2 )
            T[i][j] += (1-p) * (double)(i-j)/(j-1) * (T[i-2][j-2]+2);
        //  １枚目も２枚目もはずれ
        if ( j>=2 && j-2>=i/2 )
            T[i][j] += (1-p) * (double)(j-(i-j)-2)/(j-1) * (T[i][j-2]+1);
    }

    return T[S][S];
}};