AtCoder Grand Contest 021 题解

AtCoder Grand Contest 021

Digit Sum 2

枚举答案与 $n$ 从高到低第一个不同的位。

int main() {
	string s;
	cin >> s;
	int ans = 0;
	for (char c : s) ans += c - '0';
	for (ui i = 0; i < s.length(); i++) {
		if (s[i] == '0') continue;
		int now = s[i] - '0' - 1;
		for (ui j = 0; j < i; j++)
			now += s[j] - '0';
		now += 9 * (s.length() - i - 1);
		ans = max(ans, now);
	}
	print(ans);
	return 0;
}

Holes

先求出凸包，对于凸包内的点答案为 $0$，凸包上的点的答案为，凸包上以这个点为顶点的外角在圆中所占的比例。

const ld eps = 1e-10L, PI = acos(-1);

struct P {
	ll x, y;
	int i;
	inline P() {}
	inline P(ll x, ll y, int i) : x(x), y(y), i(i) {}
	inline P &operator += (P o) { return x += o.x, y += o.y, *this; }
	inline P &operator -= (P o) { return x -= o.x, y -= o.y, *this; }
	inline friend P operator + (P a, P b) { return a += b; }
	inline friend P operator - (P a, P b) { return a -= b; }
	inline friend bool operator < (P a, P b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
	inline friend ll operator * (P a, P b) { return a.x * b.x + a.y * b.y; }
	inline friend ll operator % (P a, P b) { return a.x * b.y - a.y * b.x; }
	inline friend ld operator ^ (P a, P b) { return a * b / a.l() / b.l(); }
	inline ld l() { return sqrt(*this * *this); }
};

int n;

inline vector<P> convex_hull(vector<P> a) {
	sort(a.begin(), a.end());
	vector<P> p;
	for (int i = 0; i < n; i++) {
		while (p.size() > 1u &&
			(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) <= 0)
				p.pop_back();
		p.pb(a[i]);
	}
	ui m = p.size();
	for (int i = n - 2; ~i; i--) {
		while (p.size() > m &&
			(p.back() - p[p.size()-2]) % (a[i] - p[p.size()-2]) <= 0)
				p.pop_back();
		p.pb(a[i]);
	}
	p.pop_back();
	return p;
}

inline ld calc(P x, P y, P z) {
	return (PI - acos((x - y) ^ (z - y))) / (2 * PI);
}

int main() {
	rd(n);
	vector<P> a;
	for (int i = 0, x, y; i < n; i++) rd(x, y), a.pb(P(x, y, i));
	a = convex_hull(a);
	vector<ld> ans(n);
	int m = a.size();
	if (m == 2) for (P o : a) ans[o.i] = 0.5;
	else for (int i = 0; i < m; i++)
		ans[a[(i+1)%m].i] = calc(a[i], a[(i+1)%m], a[(i+2)%m]);
	for (int i = 0; i < n; i++) printf("%.20Lf\n", ans[i]);
	return 0;
}

Tiling

莫名其妙的一道分类讨论贪心构造题，AGC 少有的垃圾题嗷。

const int N = 1e3 + 7;
int n, m, a, b;
char c[N][N];

#define f(p, q) c[p][q] = '^', c[p+1][q] = 'v', --b;
#define g(p, q) c[p][q] = '<', c[p][q+1] = '>', --a;

int main() {
	rd(n, m), rd(a, b);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) c[i][j] = '.';
	if (m & 1) for (int i = 1; i < n && b; i += 2) f(i, m);
	if (n > 1 && m > 2 && n & 1 && b & 1) f(n - 1, m - 2);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m - (m & 1) && b; j++)
			if (c[i][j] == '.' && c[i + 1][j] == '.') f(i, j);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m && a; j++)
			if (c[i][j] == '.' && c[i][j + 1] == '.') g(i, j);
	if (a + b) return prints("NO"), 0;
	prints("YES");
	for (int i = 1; i <= n; i++) prints(c[i] + 1);
	return 0;
}

Reversed LCS

一个结论是：$s$ 与 $s^r$ 的最长公共子序列，等于 $s$ 的最长回文子序列。

于是 $\mathcal O(n^3)$ 的区间 DP 即可，记搜的写法非常简洁。

const int N = 307, inf = 1e9;
int n, k, f[N][N][N];
char s[N];
bool v[N][N][N];

int F(int l, int r, int k) {
	if (k < 0) return -inf;
	if (r - l < 1) return r - l + 1;
	if (v[l][r][k]) return f[l][r][k];
	v[l][r][k] = 1;
	return f[l][r][k] = max(max(F(l + 1, r, k), F(l, r - 1, k)), F(l + 1, r - 1, k - (s[l] != s[r])) + 2);
}

int main() {
	rds(s, n), rd(k), print(F(1, n, k));
	return 0;
}

Ball Eat Chameleons

题意

• 有 $n$ 只变色龙，初始为蓝色。
• 有 $k$ 个球，每个球为红色或者蓝色。
• 按顺序将 $k$ 个球随机给某只变色龙吃，此时它吃下哪种颜色的球多就会变成那种颜色，如果一样多则颜色不变。
• 求有多少种方案使得最终有可能让所有变色龙都变成红色。
• $n,k \le 5 \times 10^5$，答案对 $998244353$ 取模。

题解

考虑有 $r$ 个红球 $b$ 个蓝球，有 $r + b = k$。

考虑变色龙最终为红色的两种情况：

• 它吃的红球比蓝球多。
• 它吃的红球和蓝球一样多且不为 $0$ 个，但最后吃的是蓝球。

若 $r < b$ 显然无解。

若 $r \ge b + n$，则必然有解。

否则 $b \le r < b + n$，最优的情况为有 $r-b$ 只变色龙多吃一个红球，其它 $n-(r-b)$ 只变色龙都会先吃一个红球再吃一个蓝球。

即若将 R 表示红球，B 表示蓝球，在 $b \le r < b+n$ 的情况下，一种方案满足条件当且仅当它能取出 $n-(r-b)$ 对 RB 的子序列。

等价于，将 R 看成 $+1$，B 看成 $-1$，任意一个前缀和都要 $\ge n - r$。

等价于从 $(0,0)$ 开始每次向右或者向上走到 $(r,b)$，但是不能到达 $y = x + (r - n)$ 的严格上方（即碰到 $y = x+(r-n)+1$ 这条线）的方案数。

这是一类经典的组合问题，用类似卡特兰数的计算方法（翻转从起点到第一次碰到 $y = x+(r-n)+1$ 的部分，每条不合法的路径与从 $(n-r-1,r-n+1)$ 到 $(r,b)$ 的路径一一对应）可得方案数为： $$\binom {r+b}r - \binom{r+b}{2r-n+1}$$ 于是枚举 $r$ 即可，注意 $r=b$ 的情况需要特判一下（直接将 $b$ 减 $1$ 即可，因为最后一个必须要是 B），时间复杂度 $\mathcal O(n)$。

代码

int main() {
	int n, k;
	rd(n, k);
	if (k < n) return print(0), 0;
	init(k);
	modint ans;
	for (int r = 0; r <= k; r++) {
		int b = k - r;
		if (r < b) continue;
		if (r == b) --b;
		ans += binom(r + b, r) - binom(r + b, 2 * r - n + 1);
	}
	print(ans);
	return 0;
}

Trinity

题意

• 有一个 $n \times m$ 的网格，每个格子上可以染为黑色或白色。
• 求满足下列条件的三元组 $(a_{1\dots n}, b_{1\dots m}, c_{1\dots m})$ 的个数。
  • $a_i$ 为最小的 $j$ 满足 $(i,j)$ 为黑色，若不存在则 $a_i = m + 1$。
  • $b_i$ 为最小的 $j$ 满足 $(j,i)$ 为黑色，若不存在则 $b_i = n + 1$。
  • $c_i$ 为最大的 $j$ 满足 $(j,i)$ 为黑色，若不存在则 $c_i = 0$。
• $n \le 8 \times 10^3$，$m \le 200$，答案对 $998244353$ 取模。

题解

考虑 DP，设 $f_{i,j}$ 表示 $i$ 行 $j$ 列且每行至少有一个黑色格子的三元组个数。则答案为 $\sum_{i=0}^n \binom ni f_{i,m}$。

考虑转移，每次新增 $k$ 行同时扩展一列，其中新增的 $k$ 行的前 $j$ 列都是白格子，扩展一列黑格子，原有的 $i$ 行扩展的一列可黑可白。注意这里新增的 $k$ 行可以插入在原有的 $i$ 行中间，而扩展一列是向后扩展。这样转移会包括所有可能的染色方案且没有重复，这是因为对于一种染色方案，DP 的路径有且仅有一条，即对于染色方案前 $j$ 列，有状态 $f_{i,j}$，其中 $i$ 为前 $j$ 列有黑色格子的行数。

考虑转移的系数：

• 若 $k = 0$，则相当于在第 $j+1$ 列选 $0/1/2$ 个端点，系数为 $1+i+\binom i2$。
• 若 $k > 0$，由于可能插入到中间，因此考虑第 $j+1$ 列的 $b-1$ 和 $c+1$，一定不与新增的 $k$ 行重合。贡献计数为 $\binom {i+k+2}{k+2}$，意义为从 $[0,i+k+1]$ 中选择 $k+2$ 行，其中第一行和最后一行分别作为 $b-1$ 和 $c+1$，中间 $k$ 行作为新增的 $k$ 行。

综上： $$f_{i,j} = \left(1+i+\binom i2\right)f_{i,j-1} + \sum_{k=0}^{i-1} \binom{i+2}{i-k+2}f_{k,j-1}$$ 时间复杂度 $\mathcal O(n^2m)$，无法接受。

考虑转移后半部分为卷积的形式： $$\begin{aligned} &= \sum_{k=0}^{i-1} \frac{(i+2)!}{(i-k+2)!k!}f_{k,j-1} \\\\ &= (i+2)!\sum_{k=0}^{i-1} \frac1{(i-k+2)!} \cdot \frac{f_{k,j-1}}{k!} \end{aligned}$$ NTT 优化时间复杂度为 $\mathcal O(nm\log n)$。

代码

namespace NTT {
	const int N = 1 << 21 | 1;
	const modint g = 3, vg = 1 / g;
	int n, m, k, l, r[N];
	modint vk, a[N], b[N];
	inline void ntt(modint *a, int n, modint x) {
		for (int i = 0; i < n; i++)
			if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			modint W = x ^ ((P - 1) / o);
			for (int i = 0; i < n; i += o) {
				modint w = 1;
				for (int j = 0; j < k; j++, w *= W) {
					modint x = a[i+j], y = a[i+j+k] * w;
					a[i+j] = x + y, a[i+j+k] = x - y;
				}
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		vk = (modint)1 / k;
		for (int i = 0; i < k; i++)
			r[i] = r[i>>1] >> 1 | (i & 1) << (l - 1);
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		ntt(a, k, g), ntt(b, k, g);
		for (int i = 0; i < k; i++) a[i] *= b[i];
		ntt(a, k, vg);
		for (int i = 0; i <= n + m; i++) a[i] *= vk;
	}
}

const int N = 8e3 + 7, M = 207;
int n, m;
modint f[N][M], ans;

int main() {
	rd(n, m), init(n + 2);
	f[0][0] = 1;
	for (int j = 0; j < m; j++) {
		NTT::n = NTT::m = n;
		for (int i = 0; i <= n; i++) NTT::a[i] = f[i][j] * vp[i];
		NTT::b[0] = 0;
		for (int i = 1; i <= n; i++) NTT::b[i] = vp[i+2];
		NTT::solve();
		for (int i = 0; i <= n; i++)
			f[i][j+1] = (1 + i + binom(i, 2)) * f[i][j] + p[i+2] * NTT::a[i];
	}
	for (int i = 0; i <= n; i++)
		ans += binom(n, i) * f[i][m];
	print(ans);
	return 0;
}