Codeforces #419 (Div.1) B. Karen and Test

http://codeforces.com/contest/815/problem/B

解法

和の線形性(重ね合わせの原理)を用いて計算するとうまくいく。

i 番目の要素以外を 0 として、i 番目の要素が与える影響を調べてみることにする。

f:id:pekempey:20170618143910p:plain

動的計画法により結果を得ることができるが、それでは O(n^2) であり間に合わない。よく見ると、この動的計画法の形はグリッドグラフにおける最短経路数を求める DP の形によく似ている。

適当な位置でグリッドを切り出してみよう。右下に降りるのを右移動に対応させ、左下に降りるのを下移動に対応させている。

f:id:pekempey:20170618150819p:plain

規則的に 0 が現れるので、0 を削除してみる。

f:id:pekempey:20170618151316p:plain

よって二項係数で各位置の値が求まることが分かるだろう。符号の並び方で 4 パターンのグリッドが存在するが、頑張るとなんとかなる。

二項係数で求まることはすぐ分かったんだけど、微妙なところを詰めるのに妙に時間がかかった。というか詰めきれてなくてコードがかなり汚い(他の人のコードを見た方がいい)。

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

int dp[50][50];

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

class Combination {
public:
	Combination() {
		inv.push_back(0);
		inv.push_back(1);
		f.push_back(1);
		f.push_back(1);
		invf.push_back(1);
		invf.push_back(1);
	}

	modint F(int n) {
		check(n);
		return f[n];
	}

	modint IF(int n) {
		check(n);
		return invf[n];
	}

	modint inverse(int n) {
		check(n);
		return inv[n];
	}

	modint P(int n, int r) {
		if (n < 0 || r < 0 || n < r) {
			return 0;
		}
		check(n);
		return f[n] * invf[n - r];
	}

	modint C(int n, int r) {
		if (n < 0 || r < 0 || n < r) {
			return 0;
		}
		check(n);
		return f[n] * invf[r] * invf[n - r];
	}

	modint H(int n, int r) {
		if (n == 0 && r == 0) {
			return 1;
		}
		return C(n + r - 1, r);
	}

private:
	std::vector<modint> inv;
	std::vector<modint> f;
	std::vector<modint> invf;

	void check(int k) {
		if (k < inv.size()) {
			return;
		}
		int p = inv.size() - 1;
		inv.resize(k + 1);
		f.resize(k + 1);
		invf.resize(k + 1);
		for (int i = p + 1; i <= k; i++) {
			inv[i] = inv[MOD % i] * (MOD - MOD / i);
			f[i] = i * f[i - 1];
			invf[i] = inv[i] * invf[i - 1];
		}
	}
};

void foo() {
	dp[0][0] = 1;
	for (int i = 0; i < 40; i++) {
		for (int j = 0; j < 40; j++) {
			dp[i][j + 1] += dp[i][j];
			int sgn;
			int k = (i % 4 - j % 4 + 4) % 4;
			if (k == 2 || k == 3) {
				putchar('+');
				sgn = 1;
			} else {
				putchar('-');
				sgn = -1;
			}
			dp[i + 1][j] += dp[i][j] * sgn;
		}
		puts("");
	}

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 40; j++) {
			printf("%4d", dp[i][j]);
		}
		puts("");
	}
}

Combination comb;

modint f(int i, int j, int k) {
	if (i < 0 || j < 0 || j > i) {
		return 0;
	}
	if (i == 0 && j == 0) {
		return 1;
	}

	int k1 = k + i % 2;
	int k2 = k1 + (i + 1) % 2;

	int s1 = (j + k) % 2 != 0 ? 1 : MOD - 1;
	int s2 = (j + 1 + k1) % 2 != 0 ? 1 : MOD - 1;
	int s3 = (j + 2 + k2) % 2 != 0 ? 1 : MOD - 1;

	if (s1 == 1 && s2 == 1 && s3 == MOD - 1) {
		int h = j;
		int w = i - j;
		if (h % 2 == 1 && w % 2 == 1) {
			return 0;
		}
		int sgn = 1;
		if (h % 4 == 1 && w % 4 == 2) {
			sgn = MOD - 1;
		} else if (h % 4 == 3 && w % 4 == 0) {
			sgn = MOD - 1;
		}
		return sgn * comb.C(h / 2 + w / 2, w / 2);
	}
	if (s1 == MOD - 1 && s2 == MOD - 1 && s3 == 1) {
		int h = j;
		int w = i - j;
		if (h % 2 == 1 && w % 2 == 1) {
			return 0;
		}
		int sgn = 1;
		if (h % 4 == 1 && w % 4 == 0) {
			sgn = MOD - 1;
		} else if (h % 4 == 3 && w % 4 == 2) {
			sgn = MOD - 1;
		}
		return sgn * comb.C(h / 2 + w / 2, w / 2);
	}
	return f(i - 1, j, k1) + s1 * f(i - 1, j - 1, k1);
}

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

	std::vector<modint> a(n);
	modint ans;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].n);
		ans += f(n - 1, i, 0) * a[i];
	}
	std::cout << ans.n << std::endl;
}

HourRank 20: Birjik and Nicole's Tree Game

https://www.hackerrank.com/contests/hourrank-20/challenges/birjik-and-nicoles-tree-game

解法

黒頂点を post-order でソートする。この列を左から順に見ていき、隣接する 2 点の LCA を列に挿入することを繰り返す。これだけで LCA の閉包(?)が作れる。

HL 分解は LCA を求める部分にしか使っていない。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <set>

struct HLDecomp {
	using Tree = std::vector<std::vector<int>>;
	const Tree &tree;

	std::vector<int> parent;
	std::vector<int> head;
	std::vector<int> vid;

	HLDecomp(const Tree &tree) : tree(tree) {
		const int n = tree.size();
		const int root = 0;
		std::stack<std::pair<int, int>> stack;
		stack.emplace(root, 0);

		parent.assign(n, -1);
		head.assign(n, -1);
		vid.assign(n, -1);

		std::vector<int> heavy(n, -1);
		std::vector<int> size(n, 1);
		while (!stack.empty()) {
			const int u = stack.top().first;
			const int i = stack.top().second;
			if (i < tree[u].size()) {
				stack.top().second++;
				const int v = tree[u][i];
				if (v != parent[u]) {
					parent[v] = u;
					stack.emplace(v, 0);
				}
			} else {
				stack.pop();
				int max = 0;
				for (int v : tree[u]) {
					if (v != parent[u]) {
						size[u] += size[v];
						if (max < size[v]) {
							max = size[v];
							heavy[u] = v;
						}
					}
				}
			}
		}

		std::queue<int> queue;
		queue.push(0);
		int now = 0;
		while (!queue.empty()) {
			const int h = queue.front();
			queue.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				head[i] = h;
				vid[i] = now++;
				for (int j : tree[i]) {
					if (j != parent[i] && j != heavy[i]) {
						queue.push(j);
					}
				}
			}
		}
	}

	template<typename T>
	void foreach(int u, int v, T func) {
		while (true) {
			if (vid[u] > vid[v]) {
				std::swap(u, v);
			}
			if (head[u] != head[v]) {
				func(vid[head[v]], vid[v]);
				v = parent[head[v]];
			} else {
				func(vid[u], vid[v]);
				break;
			}
		}
	}

	int lca(int u, int v) {
		while (true) {
			if (vid[u] > vid[v]) {
				std::swap(u, v);
			}
			if (head[u] != head[v]) {
				v = parent[head[v]];
			} else {
				return u;
			}
		}
	}
};

int main() {
	int n;
	std::cin >> 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);
	}

	HLDecomp hld(tree);
	int q;
	std::cin >> q;

	std::vector<int> post(n);
	std::vector<int> ord;
	std::vector<int> depth(n);
	int k = 0;

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

	std::vector<int> imos(n);
	while (q--) {
		int k;
		scanf("%d", &k);
		std::set<int> q;
		q.insert(post[0]);
		for (int i = 0; i < k; i++) {
			int t;
			scanf("%d", &t);
			t--;
			q.insert(post[t]);
			imos[t]++;
		}
		std::vector<int> a;
		std::map<int, int> parent;
		while (!q.empty()) {
			int x = ord[*q.begin()];
			q.erase(q.begin());
			a.push_back(x);
			if (!q.empty()) {
				int y = ord[*q.begin()];
				int z = hld.lca(x, y);
				if (z != y) {
					parent[y] = z;
					q.insert(post[z]);
				}
				parent[x] = z;
			}
		}
		std::vector<int> ans(k + 1);
		for (int i : a) {
			if (i != 0) {
				int p = parent[i];
				imos[p] += imos[i];
				ans[imos[i]] += depth[i] - depth[p];
			} else {
				ans[imos[i]]++;
			}
		}
		ans[0] = n;
		for (int i = 1; i < k + 1; i++) {
			ans[0] -= ans[i];
		}
		for (int i = 0; i < k + 1; i++) {
			printf("%d ", ans[i]);
		}
		printf("\n");
		for (int i : a) {
			imos[i] = 0;
		}
	}
}

World Codesprint 10: Node-Point Mappings

https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings

解法

一番左の点(複数あるなら下にある方)を根に対応させる。根を中心に偏角ソートし、たとえば部分木のサイズが [4, 5, 3] となっていたら下図のように領域を分割する。

f:id:pekempey:20170502000232p:plain

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

三点が一直線上に並ばないことと、一番左の点を中心にしているため、外積の正負を比較関数にして偏角ソート可能。

#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

https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximum-disjoint-subtree-product

解法

全方位木 DP の知名度も高まってきたので説明は省略する。以前に作成した全方位木 DP のライブラリを使用した。

#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

https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness

解法

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

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

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

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