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