yukicoder : No.2389 Cheating Code Golf

解法は割と自明かも。
https://yukicoder.me/problems/no/2389

問題

N個の問題があり、それぞれ解きたい。
各問題iにはパラメータA[i],B[i],P[i]が与えられる。

各問題を解きスコアを稼ぎたい。この時、解き方は2通りがある。

• 確実に解けるが、得られるスコアは1/A[i]
• 1/P[i]の確率で解け、得られるスコアは1/B[i]

解くのを失敗する回数がM回を超えてはならない。
最適な順で、解く問題及び解き方を選べるとき、スコアの期待値の最大値を求めよ。

解法

まだ解いてない問題のbitmaskと、許容される失敗回数を状態とし、メモ化再帰なりDPなりで解いていこう。

int N,M;
double A[12],B[12],P[12];
double dp[1<<12][41];

double hoge(int mask,int M) {
	if(mask==0) return 0;
	if(M<0) return -1e9;
	if(dp[mask][M]>=0) return dp[mask][M];
	
	double ret=0;
	int i;
	FOR(i,N) if(mask&(1<<i)) {
		double ac=hoge(mask^(1<<i),M);
		double wa=hoge(mask,M-1);
		
		ret=max(ret,A[i]+ac);
		if(wa>=0) ret=max(ret,P[i]*(B[i]+ac)+(1-P[i])*wa);
	}
	
	return dp[mask][M]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>P[i];
		A[i]=1/A[i];
		B[i]=1/B[i];
		P[i]=1/P[i];
	}
	
	int mask;
	FOR(mask,1<<N) FOR(i,M+1) dp[mask][i]=-2;
	
	_P("%.12lf\n",hoge((1<<N)-1,M));
	
}

まとめ

スコアを逆数にしたのなんでなんだろな。