SRM 548 div1 med: KingdomAndDice

オーダー落とせずに死んでました。

問題

TopCoder Statistics - Problem Statement

1 ～ X の目が書いてあり, 面が N 個あるさいころを二つ用意する。この二つのさいころの目はすべてバラバラである(よって 2*N <= X でなければならない)。
このさいころを使って簡単なゲームをする。さいころを振って, 出た目が相手の目よりも大きかったら勝ちである。
相手のさいころの目はすべて決まっているが, 自分の持っているさいころには一部目が書いてない(目が書いてないところは 0 と扱う)。勝率をなるべく 0.5 に近づけるためにさいころに目を書く(必ずしも目が書いていないところすべての目を埋めなければならないわけではない)場合, 最も条件に合う勝率はいくらか？答えが複数あり得るなら, それらのうち勝率の最も低いものを求めよ。

解法

X がだいぶでかいので,さいころの目を全部列挙することはできませんが, すでに表れている目が小さい順に vs[0], ..., vs[sz-1] と並んでいるとして, vs[i] と vs[i+1] の間が N より大きかったとすると, あり得る目として vs[i]+1, vs[i]+2, ..., vs[i]+N だけを考えれば問題ありません。このようにすると, さいころの目として考えなければならないものは O(N^2) に抑えられます。このさいころの目を列挙しておきましょう。

で, 次に dp の取り方です。dp では, dp[さいころの目の何番目までを使うか][N^2 回のうち何回勝つか][必要なさいころの目の数] = あり得るorあり得ない
というものを考えます。ただ, 必要なさいころの数は O(N) しかないので, true, false を long long に置きなおす高速化テクを使って 最後の添え字はなくしています。

ll dp[2][2555];

class KingdomAndDice {
public:
    double newFairness(vector <int> firstDie, vector <int> secondDie, int X) {
        int n = firstDie.size();
        int cnt = 0, zcnt = 0;
        for (int i = 0; i < n; i++) {
        	if (firstDie[i] == 0) zcnt++;
        	for (int j = 0; j < n; j++) {
        		if (firstDie[i] > secondDie[j]) cnt++;
        	}
        }
        vector<int> vs;
        vs.push_back(0);
        vs.push_back(X+1);
        for (int i = 0; i < n; i++) {
        	vs.push_back(firstDie[i]);
        	vs.push_back(secondDie[i]);
        }
        sort(vs.begin(), vs.end());
        vs.erase(unique(vs.begin(), vs.end()), vs.end());
        vector<int> ps;
        {
        	int sz = vs.size();
        	for (int i = 0; i < sz-1; i++) {
        		for (int j = vs[i]+1; j < min(vs[i+1], vs[i]+n+1); j++) {
        			ps.push_back(j);
        		}
        	}
        }
    	memset(dp, false, sizeof(dp));
    	int sz = ps.size();
    	for (int i = 0; i < sz; i++) {
    		int tmp = 0;
    		for (int j = 0; j < n; j++) {
    			if (ps[i] > secondDie[j]) tmp++;
    		}
    		ps[i] = tmp;
    	}
    	dp[0][cnt] = 1;
    	for (int i = 0; i < sz; i++) {
    		int cur = i%2, tar = cur^1;
    		memset(dp[tar], 0, sizeof(dp[tar]));
    		for (int j = 0; j <= n*n; j++) {
    			if (!dp[cur][j]) continue;
    			dp[tar][j] |= dp[cur][j];
    			dp[tar][j+ps[i]] |= dp[cur][j]<<1;
    		}
    	}
    	cout << cnt << endl;
    	int minValue = n*n+1, winNum = 0;
    	for (int i = 0; i <= n*n; i++) {
    		ll cover = 1ll<<(zcnt+1); --cover;
    		if (dp[sz%2][i] & cover) {
    			if (minValue > abs(n*n-2*i)) {
    				minValue = abs(n*n-2*i);
    				winNum = i;
    			}
    		}
    	}
    	return 1.*winNum/(n*n);
    }
};