TopCoder SRM 764 : Combined Hard Conquest

この650ptはDiv2基準なのかDiv1基準なのか…。
https://community.topcoder.com/stat?c=problem_statement&pm=3973&rd=17663

問題

自国にはA人の兵士がおり、敵国の3つの領地にはそれぞれO[i]人の兵士がいる。
自国にいる全兵士をどこかの領地を選択して攻め込ませる、ということを行う。
その結果、双方の兵士は与えられた確率テーブルに従い人数が減る。

敵兵士を全滅させた領地には、その後兵士を一人残さなければならない。
最適な順で攻める領地を定めたとき、全領地の敵を全滅させることができる確率はいくつか。

解法

A*O[0]*O[1]*O[2]が大した数ではないので、全状態に対し、3通り攻撃先を総当たりするだけ。
一番迷うのはテーブルの持ち方なんじゃないかな。

double dp[51][21][21][21];

class Conquest {
	public:
	
	vector<pair<pair<int,int>,double>> prob(int x,int y) {
		vector<pair<pair<int,int>,double>> R;
		if(x>3&&y>1) {
			R.push_back({{x-2,y-0},2275.0/7776});
			R.push_back({{x-1,y-1},2611.0/7776});
			R.push_back({{x-0,y-2},2890.0/7776});
		}
		if(x>3&&y==1) {
			R.push_back({{x-1,y-0},441.0/1296});
			R.push_back({{x-0,y-1},855.0/1296});
		}
		if(x==3&&y>1) {
			R.push_back({{x-2,y-0},581.0/1296});
			R.push_back({{x-1,y-1},420.0/1296});
			R.push_back({{x-0,y-2},295.0/1296});
		}
		if(x==3&&y==1) {
			R.push_back({{x-1,y-0},91.0/216});
			R.push_back({{x-0,y-1},125.0/216});
		}
		if(x==2&&y>1) {
			R.push_back({{x-1,y-0},161.0/216});
			R.push_back({{x-0,y-1},55.0/216});
		}
		if(x==2&&y==1) {
			R.push_back({{x-1,y-0},21.0/36});
			R.push_back({{x-0,y-1},15.0/36});
		}
		return R;
	}
	
	double dfs(int A,int B,int C,int D) {
		if(B+C+D==0) return 1;
		if(A<2) return 0;
		if(dp[A][B][C][D]>=0) return dp[A][B][C][D];
		double ret=0;
		if(B) {
			double tmp=0;
			auto R=prob(A,B);
			FORR(r,R) tmp+=r.second*dfs(r.first.first-(r.first.second==0),r.first.second,C,D);
			ret=max(ret,tmp);
		}
		if(C) {
			double tmp=0;
			auto R=prob(A,C);
			FORR(r,R) tmp+=r.second*dfs(r.first.first-(r.first.second==0),B,r.first.second,D);
			ret=max(ret,tmp);
		}
		if(D) {
			double tmp=0;
			auto R=prob(A,D);
			FORR(r,R) tmp+=r.second*dfs(r.first.first-(r.first.second==0),B,C,r.first.second);
			ret=max(ret,tmp);
		}
		return dp[A][B][C][D]=ret;
	}
	
	
	
	double bestChance(int armies, vector <int> opponent) {
		
		int x,y,z,i;
		FOR(i,51) FOR(x,21) FOR(y,21) FOR(z,21) dp[i][x][y][z]=-1;
		
		return dfs(armies,opponent[0],opponent[1],opponent[2]);
	}
}

まとめ

何がしたいんだ…。