Topcoder SRM 513 Div2(Medium) PerfectMemory

https://community.topcoder.com/stat?c=problem_statement&pm=11500

우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.

그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다.

처음에 실수할 수 있는 것이 뭐냐면..

실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라

하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에

답이 다르게 나온다는 사실이다.

문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한 턴수를

계산하기 위해서는 현재 남은 칸의 개수와 (이미 한번 뒤집어봐서)모양을 알고있는 칸의 개수가 중요하다는 것을 알 수가있다.

그래서 부분 문제는 이렇게 정의할 수가 있다.

dp[rest][known] : 남은칸의 수가 rest개 이고, 모양을 알고있는 칸의 수가 known 일때 클리어까지 필요한 턴수의 기대값

그럼 이제 현재 rest개가 남았고 known개를 알고있는 상황이라고 가정해보자

그러면 크게 네가지의 케이스가 있다는 것을 알 수가 있다.

우선 하나의 턴에서는 두 번 칸을 선택하는데

이미 모양을 알고있는 칸 known개는 처음 뒤집을 필요가 없다는 것이 자명하다.

1번 케이스에서는 짝을 찾았으니 rest 가 2감소할 것이고, 원래 알고있던거 하나를 없앴으니 known 은 1감소할 것이다.

2번 케이스에서도 짝을 찾았으니 rest가 2감소할 것이고, 둘다 몰랐던 칸이었으니 known 은 그대로다.

3번 케이스에서는 첫번째 고른건 처음나온거라 못없애므로 known 에 포함되며, 두번째 고른놈은 원래 알던놈이므로 바로 없애준다.

즉, 짝을 하나 지었으니 rest는 2감소하고 known은 1증가하고 1감소하므로 그대로다.

4번 케이스는 둘다 새로나온 모양이므로 짝을 못지어서 rest는 그대로, 새로알게된 모양이 2개 늘었으니 known은 2증가

각각의 케이스가 나올 확률과 다음 부분문제를 곱하여 누적해주면 부분문제가 풀린다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
class PerfectMemory {
public:
    int N,M;
    double dp[2503][2503];
    double case1(double rest, double known){
        double ret = rest-2*known;
        ret /= (rest-known);
        ret /= (rest-known-1);
        return ret;
    }
    double case2(double rest, double known){
        double ret = rest-2*known;
        ret /= (rest-known);
        ret *= (rest-2*known-2);
        ret /= (rest-known-1);
        return ret;
    }
    double case3(double rest, double known){
        double ret = rest-2*known;
        ret /= (rest-known);
        ret *= known;
        ret /= (rest-known-1);
        return ret;
    }
    double case4(double rest, double known){
        double ret = known;
        ret /= (rest-known);
        return ret;
    }
 
    double go(int rest, int known){
        if(rest==0) return 0;
        if(rest==2) return 1;
        double& cache = dp[rest][known];
        if(cache != -1) return cache;
        double ret = 0;
        if(rest/2 > known){
            ret += case1(rest, known) * (go(rest-2, known) + 1);
            ret += case2(rest, known) * (go(rest, known+2) + 1);
            ret += case3(rest, known) * (go(rest-2, known) + 2);
            ret += case4(rest ,known) * (go(rest-2, known-1) + 1);
        }
        else ret += (go(rest-2, known-1) + 1);
        return cache = ret;
    }
 
    double getExpectation(int N, int M) {
        for(int i = 0 ; i <= 2500; i++){
            for(int j = 0 ; j <= 2500; j++){
                dp[i][j] = -1;
            }
        }
        return go(N*M,0);
    }
};