TopCoder SRM 548 Div1 Medium KingdomAndDice

自分が初参戦したSRMの問題。とはいえこの時はDiv2なのでDiv1は解いてなかったのだけど。
http://community.topcoder.com/stat?c=problem_statement&pm=11986

問題

2つのN面サイコロがあり、2つ目のサイコロはすべての目が決まっている。
1つ目のサイコロは一部の目は決まっており、一部は決まっていない。

1つ目のサイコロの決まってない目に、以下の条件を満たすように目を埋めたい。

• 2つのサイコロの目は1～Xであり、同じ目は(2つのサイコロを合わせても)2つ登場しない。
• 2つのサイコロを転がしたとき、1つ目の方が大きい目が出る確率を0.5に近づけたい。

最良で、1つ目の方が大きい目が出る確率をどこまで0.5に近づけられるか。

解法

2つ目のサイコロの目の数値の間に、未確定の目の数値を埋めていくことを考える。
状態として[2つ目のサイコロの何個目の目の間か][残りの未確定の目の数][1つ目が勝つ確率*N^2]を持ち、未確定の目を埋めながらそれぞれの状態を持てるかどうかを更新するDPをしていけばよい。

最後に、持ち得る状態のうち[1つ目が勝つ確率*N^2]が(N^2)/2に一番近い状態を取ればよい。

int dp[2][51][2501];
class KingdomAndDice {
	public:
	int space[55];
	
	double newFairness(vector <int> firstDie, vector <int> secondDie, int X) {
		int N=firstDie.size(),i,j,x,y,k,left=0,tot=0;
		
		sort(firstDie.begin(),firstDie.end());
		secondDie.push_back(0);
		secondDie.push_back(X+1);
		sort(secondDie.begin(),secondDie.end());
		
		FOR(i,N+1) space[i]=min(50,secondDie[i+1]-secondDie[i]-1);
		FOR(i,N) {
			if(firstDie[i]==0) left++;
			else {
				FOR(j,N+1) {
					if(secondDie[j] < firstDie[i] && firstDie[i] < secondDie[j+1]) space[j]--, tot+=j;
				}
			}
		}
		
		space[0]=50;
		ZERO(dp);
		dp[0][left][tot]=1;
		FOR(i,N+1) {
			int cur=i%2,tar=cur^1;
			ZERO(dp[tar]);
			FOR(x,left+1) FOR(y,2501) if(dp[cur][x][y]) {
				j=min(space[i],x);
				FOR(k,j+1) dp[tar][x-k][y+k*i]=1;
			}
		}
		
		int best=2600;
		FOR(x,2501) if(dp[(N+1)%2][0][x] && abs(x-N*N/2.0)<abs(best-N*N/2.0)) best=x;
		return best/(double)(N*N);
	}
	
}

まとめ

これもなんとか自力で回答できた。