TopCoder SRM 548 Div1 Medium KingdomAndDice

TopCoder 動的計画法 確率・場合の数

問題

2個のダイスがあり、ダイスの面には数字が書かれている。
数字は以下の条件を満たす。

  • 1以上X以下
  • 書かれている数は全て互いに異なる
  • ただし、一つ目のダイスには0が何回か書かれていることがある。

いま、このダイスを使って次のようなゲームをする
先手が1番目のダイスを振り、後手が2番目のダイスを振る。
出た目の大きいほうが勝ち。


1番目のダイスの0を、まだ使われていない1からXの数字のどれかに書き換えることで、
このゲームの勝率Pを、できるだけ1/2に近づけたい。
このときの勝率Pの値を求めよ。
1/2に対して同じ近さの勝率Pが2通りあるときは、小さいほうの値を採用する。

制約条件

先手のダイスに書かれている数字は0以上X以下。
後手のダイスに書かれている数字は1以上X以下。
先手のダイスと後手のダイスの面の数は同じ。
0以外の数字は高々1度しか現れない。

方針

動的計画法による。
まずは二番目のダイスに書かれている数字を小さい順にソートする。


小さい順に並べたときのダイスの数をa[i]とすると、
一番目のダイスの0を、各a[i]について、a[i]〜a[i + 1]の中から、一つ選んで割り当てることが問題の操作に相当する。


（ただし、a[-1] = 0, a[n] = X + 1と考える）
dp[i][j][k]を、区間i番目までで、0をj個残して、今までの勝利数がkであるような状態に至れるかどうかという配列とする。
各区間ごとに0をどれだけ割り当てられるかは、min(その区間の幅, j)であるため、
この範囲でループを回せばテーブルが更新できる。


計算量はO(n^5)っぽく見えるが、
テーブルの大部分にはアクセスされないので大体O(n^4).

ソースコード

bool dp[60][60][3000];

class KingdomAndDice {
	public:
	double newFairness(vector <int> firstDie, vector <int> secondDie, int X) 
	{
		int n = firstDie.size();
		memset(dp, 0, sizeof(dp));
		
		sort(all(secondDie));
		secondDie.pb(X + 1);
		int num[60] = {}, prev = 0;
		rep(i, n + 1){
			int cnt = secondDie[i] - prev - 1;
			rep(j, n) if(prev < firstDie[j] && firstDie[j] < secondDie[i]) cnt--;
			num[i] = cnt;
			prev = secondDie[i];
		}
		
		int cnt = 0, zero = 0;
		rep(i, n) if(firstDie[i] == 0) zero++;
		rep(i, n) if(firstDie[i]) rep(j, n) if(firstDie[i] > secondDie[j]) cnt++;
		dp[0][zero][cnt] = 1;
		
		int ans = inf;
		rep(i, n + 2) rep(j, zero + 1) rep(k, 3000) if(dp[i][j][k]){
			
			int tmp = k;
			if(abs(2 * tmp - n * n) < abs(2 * ans - n * n) ||
				abs(2 * tmp - n * n) == abs(2 * ans - n * n) && tmp < ans) ans = tmp;
			
			if(i < n + 1) rep(l, min(num[i], j) + 1){
				dp[i + 1][j - l][k + i * l] = 1;
			}
		}
		return ans * 1.0 / n / n;
	}
};