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;
}
};