SRM 548 450pt : KingdomAndDice

TopCoder

問題概要

長さN(<50)の配列A,Bがある。Aの要素のいくつかは0が含まれていて、それ以外はA、Bともに要素は[1,X]の数で重複はない。Aの0になっている要素を他と被らないように[1,X]から抜きだし、A[i]>B[j]になっている(i,j)の組の個数をn*n/2になるべく近づける問題。

考えたこととか

  • 確率？とはいえ全体の個数が小さいので数え上げ問題に帰着できそう。
  • 既に確定してるのでA[i]>B[j]になっている個数を決めたら、後は0になっているのを調整するだけだ。これって簡単っぽいな。落とせない。
  • 0にどうやって重複なしで埋めていくかが問題か。
  • こういうのは小さい順に置くというルールを課すことにすれば大抵うまく行く。
    • 実際は1以上の数から順に置いて、最後に0を並べるということをしていたのだけどこれはちょっと賢くなかった。
  • dp[i][n] = {i番目までの0を確定させて、A[i]>B[j]の個数がnになるようにするのに必要な直前確定させた数の最小値}とすれば何かいけそうだ。
  • 計算量は…O(n^5*log n)とかだけど全部使うようなケースは作れないし係数も小さいので行ける。
  • 書き始める。
  • 時間がかかったけど終了5分前くらいに出せた。
  • インターミッション中にINFが小さすぎることに気づいて絶望した。
  • 最初に全部の数にnを足し込んでおけば0だけが複数回使えるという特別な処理をしなくてよいのでそうした方がよかった。

acceptされたコード(をちょっと修正したもの)

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_N = 50;
const int INF = (1<<30) - 2;

int minNumber[MAX_N + 1][MAX_N*MAX_N + 1];

struct KingdomAndDice {

	double newFairness(vector <int> firstDie, vector <int> secondDie, int X) {
		const int n = firstDie.size();
		sort(secondDie.begin(), secondDie.end());
		secondDie.push_back(X + 2*n);
		const int zeros = count(firstDie.begin(), firstDie.end(), 0);
		int wins = 0;
		for (int i = 0; i < n; ++i) if (firstDie[i] != 0) {
			for (int j = 0; j < n; ++j) if (firstDie[i] > secondDie[j]) {
				++wins;
			}
		}

		set<int> usedNums(firstDie.begin(), firstDie.end());
		usedNums.insert(secondDie.begin(), secondDie.end());
		usedNums.erase(0);

		for (int i = 0; i <= zeros; ++i) {
			fill(minNumber[i], minNumber[i] + (n*n + 1), INF);
		}

		minNumber[0][wins] = 0;
		for (int i = 0; i < zeros; ++i) {
			for (int cur = 0; cur <= n*n; ++cur) if (minNumber[i][cur] < INF) {
				minNumber[i+1][cur] = min( minNumber[i+1][cur], X + 1 );
				for (int add = 1; add <= n && cur + add <= n*n; ++add) {
					int nx = max(minNumber[i][cur] + 1, secondDie[add - 1] + 1);
					for (; nx < secondDie[add] && usedNums.find(nx) == usedNums.end(); ++nx) ;
					if (0 < nx && nx <= X && nx < secondDie[add]) {
						minNumber[i+1][cur+add] = min( minNumber[i+1][cur+add], nx );
					}
				}
			}
		}

		pair<int,int> ans(INF, INF);
		for (int i = 0; i <= n*n; ++i) if (minNumber[zeros][i] < INF) {
			ans = min( ans, make_pair(abs(n*n - 2*i), i) );
		}

		return (double)ans.second / (n * n);
	}

};