World Codesprint 10: Node-Point Mappings

解法

これを再帰的に繰り返すことでかならず構築できる。

#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>
#include <complex>

using P = std::complex<long long>;

long long cross(const P &a, const P &b) {
return imag(conj(a) * b);
}

std::vector<std::vector<int>> readTree(int n) {
std::vector<std::vector<int>> tree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
return tree;
}

std::vector<P> readPoints(int n) {
std::vector<P> points(n);
for (int i = 0; i < n; i++) {
long long x, y;
scanf("%lld %lld", &x, &y);
points[i].real(x);
points[i].imag(y);
}
return points;
}

int main() {
int n;
std::cin >> n;

auto tree = readTree(n);
auto points = readPoints(n);

std::vector<P> map(n);
std::vector<int> size(n);

std::function<void(int, int)> dfs = [&](int u, int p) {
size[u] = 1;
for (int v : tree[u]) {
if (v != p) {
dfs(v, u);
size[u] += size[v];
}
}
};
dfs(0, -1);

std::function<void(int, int, std::vector<P>)> dfs2 = [&](int u, int p, std::vector<P> ps) {
auto it = min_element(ps.begin(), ps.end(), [&](const P &a, const P &b) {
return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
});
P min = *it;
ps.erase(it);
std::sort(ps.begin(), ps.end(), [&](const P &a, const P &b) {
return cross(a - min, b - min) < 0;
});
map[u] = min;

int k = 0;
for (int i = 0; i < tree[u].size(); i++) {
const int v = tree[u][i];
if (v == p) {
continue;
}
std::vector<P> next;
for (int j = 0; j < size[v]; j++) {
next.push_back(ps[k++]);
}
dfs2(v, u, next);
}
};
dfs2(0, -1, points);

for (int i = 0; i < n; i++) {
int j = std::find(points.begin(), points.end(), map[i]) - points.begin();
std::cout << j + 1 << " ";
}
}


World Codesprint 10: Maximum Disjoint Subtree Product

解法

#include <iostream>
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>

// add :: T -> T -> T
//     {v1,v2,...,vm}+vm+1
// bundle :: T -> T
//     u->{v1,v2,v3,...,vm}
template<class T, class F1, class F2>
std::vector<T> freeTreeDP(const std::vector<std::vector<int>> &g, F1 add, F2 bundle) {
const int n = g.size();
std::vector<T> dp(n);
std::function<void(int, int)> dfs = [&](int u, int p) {
for (int v : g[u]) {
if (v != p) {
dfs(v, u);
dp[u] = add(dp[u], dp[v]);
}
}
dp[u] = bundle(dp[u], u);
};
dfs(0, -1);
std::function<void(int, int)> dfs2 = [&](int u, int p) {
const int m = g[u].size();
T l;
std::vector<T> r(m);
for (int i = m - 2; i >= 0; i--) {
r[i] = add(dp[g[u][i + 1]], r[i + 1]);
}
for (int i = 0; i < m; i++) {
const int v = g[u][i];
dp[u] = bundle(add(l, r[i]), u);
l = add(l, dp[v]);
if (v != p) {
dfs2(v, u);
}
}
dp[u] = bundle(l, u);
};
dfs2(0, -1);
return dp;
}

int main() {
const long long INF = 1e18;
struct foo {
long long max = -INF;
long long min = INF;
long long maxc = -INF;
long long minc = INF;
long long maxp;
long long minp;
};

int n;
std::cin >> n;

std::vector<long long> w(n);
for (int i = 0; i < n; i++) {
scanf("%lld", &w[i]);
}

std::vector<std::vector<int>> tree(2 * n - 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--;
v--;
tree[u].push_back(i + n);
tree[i + n].push_back(u);
tree[v].push_back(i + n);
tree[i + n].push_back(v);
}

auto add = [&](const foo &a, const foo &b) {
foo c;
c.max = std::max(a.max, b.max);
c.min = std::min(a.min, b.min);
c.maxc = std::max(0LL, a.maxc) + std::max(0LL, b.maxc);
c.minc = std::min(0LL, a.minc) + std::min(0LL, b.minc);
c.maxp = a.max * b.max;
c.minp = a.min * b.min;
return c;
};

auto bundle = [&](const foo &a, int id) {
foo c;
if (id < n) {
c.maxc = std::max(a.maxc + w[id], w[id]);
c.minc = std::min(a.minc + w[id], w[id]);
c.max = std::max(a.max, c.maxc);
c.min = std::min(a.min, c.minc);
} else {
c = a;
}
return c;
};

auto dp = freeTreeDP<foo>(tree, add, bundle);

long long ans = -1e18;
for (int i = n; i < 2 * n - 1; i++) {
ans = std::max(ans, std::max(dp[i].maxp, dp[i].minp));
}
std::cout << ans << std::endl;
}


World Codesprint 10: Permutation Happiness

解法

DP。1～n の順列に n+1 を挿入するイメージで更新していく。山の頂上（極大点）の個数を状態として持つと良い。dp[i: 順列のサイズ][j: 頂上の個数] とする。

(1) 頂上の隣に挿入した場合は、頂上の個数は変わらない。2j 通り。

(2) それ以外の場所に挿入すると、頂上の個数が一つ増える。i+1-2j 通り。

#include <iostream>
#include <cstdio>
#include <vector>

const int mod = 1e9 + 7;

struct modint {
int n;
modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

int main() {
int q;
std::cin >> q;

const int N = 3000;

std::vector<std::vector<modint>> dp(N + 1, std::vector<modint>(N + 1));

dp[1][1] = 1;

for (int i = 1; i < N; i++) {
for (int j = 0; j <= i; j++) {
dp[i + 1][j] += dp[i][j] * (2 * j);
dp[i + 1][j + 1] += dp[i][j] * (i + 1 - 2 * j);
}
}

while (q--) {
int n, k;
std::cin >> n >> k;

modint ans = 0;
for (int i = 0; i <= N; i++) {
if (n - i >= k) {
ans += dp[n][i];
}
}
std::cout << ans.n << std::endl;
}
}