Codeforces #1028 : Div1 C. Gellyfish and Eternal Violet

だいぶ苦戦した。
https://codeforces.com/contest/2115/problem/C

問題

N体のモンスターがおり、i番のモンスターのHPはH[i]である。
全部のモンスターのHPを1にしたい。

以下の手順をm回行うとき、最適手を取って条件を達成できる確率を求めよ。

• まず、剣が輝くかどうか確率pで定まる
• 剣の状態がわかったうえで、以下のいずれかを選ぶ。
  • 何もしない
  • 剣が輝いている場合、全部の敵のHPを1減らす
  • 剣が輝いていない場合、指定した敵のHPを1減らす

解法

まず敵のHPを、最小値に合わせることを考える。
最小値が2より大きく、かつ全敵のHPが最小値に一致しない場合は、剣が輝こうが輝くまいがとにかく敵のHPを減らす方向に走る。
f(m,v) := 敵のHPの最小値がm、最小値からの差分の総和がvとなる状態に至る確率
なお、m,vの状態に至るまでの手数はあきらか。

一端全敵のHPがそろうと、以後は最小値からの差分の総和は高々Nにしかならない。
そこであとは以下をDPで埋めて行く。
g(s,m,v) := s回処理を行い、敵のHPの最小値がm、最小値からの差分の総和がvとなる状態に至る確率

int T,N,M,P;
int H[404];
double PP;

double d[404][4040];
double dp[4040][404][20];
double dp2[4040][4040];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>P;
		PP=P/100.0;
		FOR(i,N) {
			cin>>H[i];
			H[i]--;
		}
		
		sort(H,H+N);
		x=H[0];
		y=0;
		FOR(i,N) y+=H[i]-x;
		
		double ret=0;
		if(x==0&&y==0) {
			ret=1;
		}
		else if(y<=M) {
			FOR(i,x+1) FOR(j,y+1) d[i][j]=0;
			d[x][y]=1;
			for(j=y;j>=1;j--) {
				for(i=x;i>=1;i--) {
					d[i-1][j]+=PP*d[i][j];
					d[i][j-1]+=(1-PP)*d[i][j];
				}
			}
			//余剰がない
			FOR(i,x+1) FOR(j,N+1) dp[0][i][j]=0;
			dp[0][0][0]=1;
			for(k=1;k<=M-y;k++) {
				FOR(i,x+1) FOR(j,N) {
					if(i&&j) {
						dp[k][i][j]=PP*dp[k-1][i-1][j]+(1-PP)*dp[k-1][i][j-1];
					}
					else if(i) {
						dp[k][i][j]=PP*dp[k-1][i-1][j]+(1-PP)*max(dp[k-1][i-1][N-1],dp[k-1][i][j]);
					}
					else if(j) {
						dp[k][i][j]=PP*dp[k-1][i][j]+(1-PP)*dp[k-1][i][j-1];
					}
					else {
						dp[k][i][j]=1;
					}
				}
			}
			for(i=1;i<=x;i++) if(M-(x+y)+(i+0)>=0) ret+=d[i][0]*dp[M-(x+y)+(i+0)][i][0];
			//1がある
			FOR(i,y+1) dp2[0][i]=0;
			dp2[0][0]=1;
			for(k=1;k<=M-x;k++) {
				dp2[k][0]=1;
				for(i=1;i<=y;i++) {
					dp2[k][i]=PP*dp2[k-1][i]+(1-PP)*dp2[k-1][i-1];
				}
			}
			for(i=1;i<=y;i++) if(M-(x+y)+i>=0) ret+=d[0][i]*dp2[M-(x+y)+i][i];
			
		}
		
		_P("%.12lf\n",ret);
	}
		
}

まとめ

2ステップに分けてDPをしていくのがコツ。