Visits: 2677

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)

Weekly Records

模拟。

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int s = 0;
        for (int j = 1; j <= 7; j++) {
            int x;
            cin >> x;
            s += x;
        }
        cout << s << " \n"[i==n];
    }
    return 0;
}

racecar

模拟。

int main() {
    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    bool ok = 0;
    auto check = [&](string s) {
        string t = s;
        reverse(t.begin(), t.end());
        return s == t;
    };
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && check(a[i] + a[j])) ok = 1;
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}

Ideal Sheet

主要思路就是枚举两张图的相对位置，然后合并起来。

Trick 1：转化为坐标，这样就只是在数上加减，也不用考虑数组负数下标的问题。

Trick 2：保证所有有效部分顶在最上和最左。

int main() {
    auto in = [&]() {
        int n, m;
        cin >> n >> m;
        vector<string> s(n);
        for (auto &a : s) cin >> a;
        int u = n, v = m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (s[i][j] == '#')
                    u = min(u, i), v = min(v, j);
        set<pi> st;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (s[i][j] == '#')
                    st.insert(mp(i - u, j - v));
        return st;
    };
    set<pi> sa = in(), sb = in(), sx = in();
    for (int dx = -10; dx <= 10; dx++)
        for (int dy = -10; dy <= 10; dy++) {
            set<pi> sy;
            for (auto o : sa)
                sy.insert(mp(o.fi - min(dx, 0), o.se - min(dy, 0)));
            for (auto o : sb)
                sy.insert(mp(o.fi + max(dx, 0), o.se + max(dy, 0)));
            if (sx == sy) return cout << "Yes" << endl, 0;
        }
    cout << "No" << endl;
    return 0;
}

Mismatched Parentheses

贪心地匹配括号。

int main() {
    int n;
    string s, ans;
    cin >> n >> s;
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') ++c, ans.pb(s[i]);
        else if (s[i] == ')') {
            if (c) {
                while (ans.back() != '(') ans.pop_back();
                ans.pop_back();
                --c;
            } else ans.pb(s[i]), c = 0;
        } else ans.pb(s[i]);
    }
    cout << ans << endl;
    return 0;
}

Distinct Adjacent

$n$ 较小时单独处理，$n$ 较大时递推，设 $f_n$ 为答案。

讨论第一个数与第 $n-2$ 个数的关系，若相同则方案数为 $(m-1)f_{n-2}$，若不同则方案数为 $(m-2)f_{n-1}$。

int main() {
    int n, m;
    cin >> n >> m;
    if (n == 2) {
        cout << 1ll * m * (m - 1) % P << endl;
        return 0;
    }
    if (n == 3) {
        cout << 1ll * m * (m - 1) % P * (m - 2) % P << endl;
        return 0;
    }
    vector<modint> f(n + 1);
    f[2] = 1ll * m * (m - 1) % P, f[3] = 1ll * m * (m - 1) % P * (m - 2) % P;
    for (int i = 4; i <= n; i++) f[i] = f[i-2] * (m - 1) + f[i-1] * (m - 2);
    cout << f[n].x << endl;
    return 0;
}

Virus 2

每次实际上是做一个多源最短路。

唯一的问题是，如果我们维护源点，最坏情况是每次扫描 $\mathcal O(n)$ 个点，时间复杂度为 $\mathcal O(nd)$。

考虑维护所有已被传染的点和未被传染的点之间的边，每次只需要从 $\le x_i$ 的边对应的未被传染的点开始做多源最短路即可。由于所有边至多被扫描一次，这部分时间复杂度为 $\mathcal O(m)$。

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pi>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].pb(mp(y, z));
        e[y].pb(mp(x, z));
    }
    int k;
    cin >> k;
    vi d(n + 1, -1);
    pq<pi> q;
    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        d[x] = 0;
        for (auto o : e[x])
            q.push(mp(-o.se, o.fi));
    }
    cin >> k;
    for (int t = 1; t <= k; t++) {
        int w;
        cin >> w;
        pq<pi> p;
        while (q.size() && -q.top().fi <= w) {
            int x = q.top().se, r = w + q.top().fi;
            q.pop();
            if (~d[x]) continue;
            p.push(mp(r, x));
        }
        while (p.size()) {
            int x = p.top().se, r = p.top().fi;
            p.pop();
            if (~d[x]) continue;
            d[x] = t;
            for (auto o : e[x]) {
                int y = o.fi, z = o.se;
                if (z > r) q.push(mp(-z, y));
                else p.push(mp(r - z, y));
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << d[i] << endl;
    return 0;
}

Approximate Equalization

先算出最后结果的结构，注意对负数的处理。

然后就是 trivial 的 $\mathcal O(n^2)$ DP，$f_{i,j}$ 表示前 $i$ 个数转换成 $j$ 个较小值的最小步数，转移就是讨论当前数转换为较小值还是较大值。转移写出来后发现 abs 中的内容实际上是一样的。

int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i-1] + a[i];
    ll w = s[n] / n, t = s[n] % n;
    if (t < 0) w--, t += n;
    vector<vector<ll>> f(n + 1, vector<ll>(t + 1, 1e18));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= t; j++) {
            f[i][j] = f[i-1][j] + abs(a[i] + s[i-1] - w * (i - 1) - j - w);
            if (j) f[i][j] = min(f[i][j], f[i-1][j-1] + abs(a[i] + s[i-1] - w * (i - 1) - (j - 1) - (w + 1)));
        }
    cout << f[n][t] << endl;
    return 0;
}

Marquee

带通配符的字符串匹配模板：P4173 残缺的字符串。