0232-Life Game

PC甲子園本戦では解けなかった問題。

あるマスにある金額を持って止まった時の期待値をDPで求めていく。
メモ化探索のメモのミスで4回ぐらいWAになってしまった

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long double ld;
#define MEMCLEAR(variable_d) memset(variable_d,0,sizeof(variable_d))
int X,Y,Z;
int V[4];
enum EVENT{NONE,GO,GET,LOSS};
struct MASS{
	EVENT e;
	int val;
};
ld prediv;
MASS M[100];

ld rec[65][5001];
void clearrec(){
	for(int i=0;i<65;i++){
		for(int j=0;j<5001;j++){
			rec[i][j]=-1;
		}
	}
}
//解答
ld slove(int now,int money){
	ld ret=0;
	int oldnow=now,oldmoney=money;
	if(rec[oldnow][oldmoney]>=0.0)return rec[oldnow][oldmoney];
	//イベントの処理
	if(M[now].e==GO){
		now+=M[now].val;
	}else if(M[now].e==GET){
		money+=M[now].val;
	}else if(M[now].e==LOSS){
		money-=M[now].val;
		if(money<0)money=0;
	}
	if(now>=Y){//ゴール
		ret=(ld)money;
	}else{
		for(int i=0;i<X;i++){
			ret+=slove(now+V[i],money)*prediv;
		}
	}
	return rec[oldnow][oldmoney]=ret;
}
int main(){
	int N,E,A;
	for(;scanf("%d%d%d",&X,&Y,&Z),(X|Y|Z);){
		for(int i=0;i<X;i++)scanf("%d",&V[i]);
		MEMCLEAR(M);
		for(int i=0;i<Z;i++){
			scanf("%d%d%d",&N,&E,&A);
			M[N].e=(EVENT)E;
			M[N].val=A;
		}
		prediv=(ld)1.0/(ld)X;
		clearrec();
		printf("%d\n",(int)floor(slove(0,0)+1e-4));
		fflush(stdout);
	}
	return 0;
}