TCO '09 Round 3 Medium CampaignTrail

問題概要

n個の州がある国で選挙を行う。
州について0,1,2...順番に選挙を行い、その州で勝った場合electors[i]人の表が得られる。

それぞれの州には、選挙のキャンペーンすることができて、
しなかった場合の勝率winCurrent[i]およびした場合の勝率winIfVisited[i]が与えられる。

visits個の州でキャンペーンをすることができて、ある州でキャンペーンをするか否かは、それまでの選挙結果を元にして決めることができる。

このとき、最善を尽くした場合に選挙で過半数の票を得られる確率を求めよ。

制約条件

州の数≦50,
electors[i]≦50

方針

得票の総数が2500以下、州が50以下なのでDPで解ける気がしてくる。
また、選挙の終わりのほうからテーブルを決定していけば、最善を尽くす確率も計算できるような気がしてくる。

確率のDPはDPの中でも特に苦手。。。
うっすらと方針はわかるのに、どこをどう掛け算すると正しい確率になるのか分からないことが多い。

dp[i][j][k]を、i箇所目まで見て、あとj箇所訪れられて、あとk票得る必要があるときの勝率とする。
この表をi=n-1から逆順に更新していくことで答えが求められる。

ソースコード

double dp[51][51][2501];

class CampaignTrail {
public:
  double probWin(vector <int> electors, vector <int> winCurrent, vector <int> winIfVisited, int visits) {
  	
  	int n=electors.size(), sum=accumulate(electors.begin(),electors.end(),0);
  	
  	rep(i,n+1)rep(j,visits+1)rep(k,sum+1)dp[i][j][k]=k>sum/2?1:0;
  	
  	for(int i=n-1;i>=0;i--)rep(j,visits+1)rep(k,sum+1-electors[i]){
  		
  		double p1=winCurrent[i]/100.0, p2=winIfVisited[i]/100.0;
  		
  		dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k]*(1-p1) + dp[i+1][j][k+electors[i]]*p1);
  		
  		if(j+1<=visits)
  		dp[i][j][k]=max(dp[i][j][k],dp[i+1][j+1][k]*(1-p2) + dp[i+1][j+1][k+electors[i]]*p2);
  		
  	}
  	
    return dp[0][0][0];
  }
};