TopCoder SRM 343 Div1 Medium MoneyGame
問題
3種類の硬貨があり、それぞれの価値はvalue[i]である。
先手がi枚目のコインをlennysCoins[i]枚もって、
後手がi枚目のコインをfredsCoins[i]枚もって、次のようなゲームを行う。
- ポットに手持ちから一枚コインを入れる
- 入れたコインの価値より小さい額のコインをポットから取り出す
- コインを入れられなくなったプレイヤーの負け
- 負けたプレイヤーは、その時点で相手が持っているお金の総額だけ負ける
お互いが最善を尽くすとき、先手は最大でどれだけの金額勝てるか(負けるなら損を最小に)求めよ。
勝ちの場合はその金額を、負けの場合はその金額にマイナスを付けて返せ。
制約条件
コインは3種類
lennysCoins[i],fredsCoins[i]≦5
value[i]≦1000
方針
手番のプレイヤーの手持ちのお金は常に減るため、ゲームは必ず終了する。
したがって、min-max探索をすればよい。
探索のメモにmapを使うとTLE.
配列に詰め込んだら通った。
ソースコード
vi val; const int MX=11*11*11*11*11*11*2; int dp[MX]; inline int pack(const vi &v,int t){ int res=0; rep(i,6)res*=11, res+=v[i]; return res*2+t; } int rec(vi coin,int turn){ if(dp[pack(coin,turn)]!=inf)return dp[pack(coin,turn)]; int ans=-inf, enemy=0, lose=1; rep(i,3)enemy+=val[i]*coin[i+(1-turn)*3]; rep(i,3)if(coin[i+turn*3]){ lose=0; coin[i+turn*3]--; coin[i+6]++; rep(a,coin[6]+1)rep(b,coin[7]+1)rep(c,coin[8]+1){ int sum=a*val[0]+b*val[1]+c*val[2]; if(sum>=val[i])continue; coin[6]-=a; coin[7]-=b; coin[8]-=c; coin[turn*3]+=a; coin[turn*3+1]+=b; coin[turn*3+2]+=c; ans=max(ans,-rec(coin,1-turn)); coin[turn*3]-=a; coin[turn*3+1]-=b; coin[turn*3+2]-=c; coin[6]+=a; coin[7]+=b; coin[8]+=c; } coin[i+turn*3]++; coin[i+6]--; } if(lose)ans=-enemy; return dp[pack(coin,turn)]=ans; } class MoneyGame { public: int play(vector <int> lennysCoins, vector <int> fredsCoins, vector <int> values) { val=values; rep(i,MX)dp[i]=inf; vi coin; rep(i,3)coin.pb(lennysCoins[i]); rep(i,3)coin.pb(fredsCoins[i]); rep(i,3)coin.pb(0); return rec(coin,0); } };