World Codesprint 10: Node-Point Mappings
https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings
解法
一番左の点(複数あるなら下にある方)を根に対応させる。根を中心に偏角ソートし、たとえば部分木のサイズが [4, 5, 3] となっていたら下図のように領域を分割する。
これを再帰的に繰り返すことでかならず構築できる。
三点が一直線上に並ばないことと、一番左の点を中心にしているため、外積の正負を比較関数にして偏角ソート可能。
#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 通り。
(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; } }
GCJ 2017 Qual
A 問題
+- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。
B 問題
10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁の数字を 1 減らしたらそれに続く数字はすべて 9 にすればいいことを踏まえれば解くことができる。
C 問題
区間の長さだけ保持しておけばよくて、大きい区間から順に分割していくのを繰り返せば良い。 分割過程では値が重複しやすいため、同じ長さの区間をまとめて処理すれば速くなりそうである。
分割の様子を図にすると以下の通り。
木の高さは O(log n) である。また、各レベルにおける値の種類数はたかだか 2 である(これは最大値と最小値の差がたかだか 1 であることから分かる)。ゆえにまとめて処理すれば O(log n) 回で収まる。
D 問題
条件を整理すると
- どの列/行も、x を 2 つ以上含まない
- どの列/行も、x と o の両方を同時に含まない
- どの列/行も、o を 2 つ以上含まない
- どの対角線も、+ を 2 つ以上含まない
- どの対角線も、+ と o の両方を同時に含まない
- どの対角線も、o を 2 つ以上含まない
となる。あるマスに o が書かれているというのは、あるマスに + と x の両方が書かれていると言い換えられる。この言い換えにより条件はよりシンプルになる。
- どの列/行も、x を 2 つ以上含まない
- どの対角線も、+ を 2 つ以上含まない
+/x を o に変える操作は許されているので、+/x は完全に独立して考えることができる。よって、それぞれ独立に最大化すればよい。これは貪欲にできる。
AtCoder Grand Contest 012 C: Tautonym Puzzle
http://agc012.contest.atcoder.jp/tasks/agc012_c
解法
空の列も良い文字列だとみなす。
順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。
- A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。
- A←A+[foo], B←[foo]+B とすると A+B のパターン数は X+1 になる。
これを利用することで 4log(N) 個の要素で構築できる。