TopCoder SRM 636 Hard

2017-02-26 | [Competitive programming]

概要

数列 S に対して，i < j かつ S[i] < S[j] を満たす組 (i, j) の個数を sortedness と呼ぶ．

1～N の permutation のうち何箇所か (14 箇所以下) の値が消されてわからなくなっている．わからなくなっている箇所を適当に補って，sortedness を与えられた値に等しくする方法は何通りあるか？

解法

消されている数を，小さい方半分と大きい方半分に分ける．それぞれの集合を L, R とする．

L の要素を入れる場所を決めると (最大 C(14, 7) 通り)，L の要素と R の要素の組によって生じる sortedness の値は一意に定まることに注意する．なので，L の要素を入れる場所を決めたときに，その中で L の順番を入れ替えて得られる sortedness (L の要素同士 / L の要素と既存の数によって生じるものたち) としてあり得るものを全部列挙しておき， R についても同様のことをすると，L について得られた sortedness と結びつくべき R の位置 / sortedness は一意に決まるので，わりと速く解ける．

コード

int N, U;
vector<int> seq;
bool used[2020];
vector<int> unusedV;
vector<int> unusedL;
int bonus[15][15]; // bonus[i][j]: sortedness added when unusedV[i] is placed to unusedL[j]


vector<pair<int, int> > dicL[1 << 14], dicH[1 << 14];

void generate_dic(vector<pair<int, int> > *dest, int lo, int hi)
{
	vector<vector<int> > perms;
	vector<int> bns;
	vector<int> seq;
	for (int i = 0; i < hi - lo; ++i) seq.push_back(i);
	do {
		perms.push_back(seq);
		int b = 0;
		for (int i = 0; i < seq.size(); ++i) {
			for (int j = i + 1; j < seq.size(); ++j) {
				if (seq[i] < seq[j]) ++b;
			}
		}
		bns.push_back(b);
	} while (next_permutation(seq.begin(), seq.end()));

	for (int i = 0; i < (1 << U); ++i) if (__builtin_popcount(i) == hi - lo) {
		vector<int> locs;
		for (int j = 0; j < U; ++j) if (i & (1 << j)) locs.push_back(j);

		vector<int> scores;
		for (int j = 0; j < perms.size(); ++j) {
			int bn = bns[j];
			for (int k = 0; k < hi - lo; ++k) {
				bn += bonus[perms[j][k] + lo][locs[k]];
			}
			scores.push_back(bn);
		}
		sort(scores.begin(), scores.end());

		int last = -1, ch = 0;
		for (int j = 0; j < scores.size(); ++j) {
			if (last != scores[j]) {
				if (last != -1) dest[i].push_back({ last, ch });
				last = scores[j];
				ch = 1;
			} else ++ch;
		}
		dest[i].push_back({ last, ch });
	}
}

class Sortish {
public:
    long long ways(int sn, vector <int> seq_) {
		seq = seq_;
		N = seq.size();

		for (int i = 0; i < N; ++i) used[i + 1] = false;
		for (int i = 0; i < N; ++i) if (seq[i] != 0) used[seq[i]] = true;
		for (int i = 1; i <= N; ++i) if (!used[i]) unusedV.push_back(i);
		for (int i = 0; i < N; ++i) if (seq[i] == 0) unusedL.push_back(i);

		int already = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				if (seq[i] != 0 && seq[j] != 0 && seq[i] < seq[j]) ++already;
			}
		}

		U = unusedV.size();
		for (int i = 0; i < U; ++i) {
			for (int j = 0; j < U; ++j) {
				int s = 0;
				for (int k = 0; k < unusedL[j]; ++k) {
					if (seq[k] != 0 && seq[k] < unusedV[i]) ++s;
				}
				for (int k = unusedL[j] + 1; k < N; ++k) {
					if (seq[k] != 0 && unusedV[i] < seq[k]) ++s;
				}
				bonus[i][j] = s;
			}
		}

		int lo = U / 2, hi = U - U / 2;
		generate_dic(dicL, 0, lo);
		generate_dic(dicH, lo, U);

		i64 ret = 0;
		for (int p = 0; p < (1 << U); ++p) if (dicL[p].size() > 0) {
			int q = ((1 << U) - 1) ^ p;
			int target = sn - already;
			for (int i = 0; i < U; ++i) {
				for (int j = i + 1; j < U; ++j) {
					if (((p >> i) & 1) && ((q >> j) & 1)) --target;
				}
			}

			int i = 0, j = (int)dicH[q].size() - 1;
			while (i < dicL[p].size() && j >= 0) {
				int sum = dicL[p][i].first + dicH[q][j].first;
				if (sum < target) ++i;
				else if (sum > target) --j;
				else {
					ret += (i64)dicL[p][i].second * dicH[q][j].second;
					++i; --j;
				}
			}
		}
		return ret;
	}
};