Visits: 1778

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