Codeforces Round #660 (Div. 2) 感想

Dashboard - Codeforces Round #660 (Div. 2) - Codeforces

ABCDの4完。レート変動は 1896->1939 (+43)。

いぇ～～い紫に復帰したぜ～～

A - Captain Flint and Crew Recruitment

nealy prime は小さいものから 6, 10, 14, 15。なので、 $n \le 30$ なら NO。

$n \gt 30$ なら YES で、ほとんどの場合は 6, 10, 14, 30-n を出力すればいいんだけど、 $n = 36, 40, 44$ のときは 30-n が 6, 10, 14 のいずれかと重複してしまうので、これらは個別に対応する。

計算量は $O(1)$ 。

これはわりかし早く解けた。うれしい。

提出コード

リンク： http://codeforces.com/contest/1388/submission/88453710

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N;
        cin >> N;
        if (N <= 30) {
            prints()("NO");
        }
        else if (N == 36) {
            prints()("YES");
            prints()(6, 10, 15, 5);
        }
        else if (N == 40) {
            prints()("YES");
            prints()(6, 10, 15, 9);
        }
        else if (N == 44) {
            prints()("YES");
            prints()(6, 10, 15, 13);
        }
        else {
            prints()("YES");
            prints()(6, 10, 14, N - 30);
        }
    }
}

B - Captain Flint and a Long Voyage

$r$ を最大化するためには少なくとも $x$ の各桁は 4bit 幅を死守しなければならない。

そうなると、とれる選択肢は 8 か 9 だけで、消去される桁に重なる部分を 8、それ以外を 9 にすればいい。

計算量は $O(n)$ 。

せっかくAを早めに解けたのに、この問題で時間をかけすぎてしまった......。解き終わって順位表を見ると 2000位くらいで冷や汗を書いた。

提出コード

リンク：http://codeforces.com/contest/1388/submission/88476616

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N;
        cin >> N;
        string ans;
        for (ll i = 0; i < N * 3 / 4; i++) {
            ans += '9';
        }
        while ((ll)ans.size() < N) {
            ans += '8';
        }
        prints()(ans);
    }
}

C - Uncle Bogdan and Country Happiness

むずかしかった。問題文も難しいし長いしつらかった。

DFSで葉から根に向かって実現可能性を調べていく。

子孫を持たない町（葉の町）の状態は $p_i$ と $h_i$ だけで完全に決定される。 $h_i - p_i \gt 0$ または $h_i + p_i \lt 0$ または $p_i - h_i$ が奇数のときは実現不可能。そうでないときは実現可能で、この町の bad mood な人の人数を $(p_i - h_i) / 2$ 、good mood な人の人数を $(p_i + h_i) / 2$ にすればいい。

次に、子孫を持つ町について考える。

$i$ 町の子の町ではすでに何人が good mood で何人が bad mood なのかが決まっている。子の町すべてにおける good mood な人の人数の和を $g$ 、bad mood な人の人数の和を $b$ とおく。このとき、 $i$ 町を通過または停止する人数 $t_i$ は、

$\displaystyle{ t_i = p_i + g + b }$

と書ける。このうち、 $i$ 町に住む $p_i$ 人と子の町において bad mood な人々 $b$ 人については $i$ 町で good mood および bad mood の両方を取りえるけど、子の町において good mood な人々 $g$ 人は $i$ 町では good mood しか取りえない（一度損ねた機嫌は二度と戻らないので）。

よって、 $i$ 町の幸せ指数の実現可能性は次のように判断できる：

$(h_i - g) - (p_i + b) \gt 0$ または $(h_i - g) + (p_i + b) \lt 0$ または $(p_i + b) - (h_i - g)$ が奇数のとき、実現不可能。
そうでないとき実現可能で、bad mood な人の人数を $\displaystyle \frac{(p_i + b) - (h_i - g)}{2}$ 、 good mood な人の人数を $\displaystyle \frac{(p_i + b) + (h_i - g)}{2} + g$ にすればいい。

全ての町について幸せ指数が実現可能なら YES、無理なら NO を出力する。

計算量は $O(n)$ 。

提出コード

リンク： http://codeforces.com/contest/1388/submission/88504721

ll N, M;
Vl P, H;
using Graph = vector<Vi>;
Graph g;
bool ok;
 
Pll dfs(int idx, int par) {
    if ((ll)g[idx].size() == 1 && g[idx][0] == par) {
        if (P[idx] - H[idx] < 0 || P[idx] + H[idx] < 0 || (P[idx] - H[idx]) & 1) {
            ok = false;
            return {0, 0};
        }
        return {P[idx], (P[idx] - H[idx]) / 2};
    }
    ll sp = 0, sb = 0;
    for (auto v : g[idx]) {
        if (!ok) return {0, 0};
        if (v == par) continue;
        auto [p, b] = dfs(v, idx);
        sp += p, sb += b;
    }
    ll x = H[idx] - (sp - sb);
    ll a = P[idx] + sb;
    if (a - x < 0 || a + x < 0 || (a - x) & 1) {
        ok = false;
        return {0, 0};
    }
    return {P[idx] + sp, (a - x) / 2};
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        cin >> N >> M;
        P.resize(N), H.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> P[i];
        }
        for (ll i = 0; i < N; i++) {
            cin >> H[i];
        }
        g.assign(N, Vi());
        for (ll i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        ok = true;
        dfs(0, -1);
        cout << (ok ? "YES\n" : "NO\n");
    }
}

D - Captain Flint and Treasure

$a_i$ がすべて非負ならトポロジカル順に操作するだけだけど、負も許されているから少し考える必要がある。

$b_j = i$ である $j$ が $i$ より先に操作されると、 $\mathrm{ans}$ には $a_i$ に $a_j$ を加えたものが足しこまれる。逆にそうしなければ $\mathrm{ans}$ には「 $a_i$ に $a_j$ を加えた」ことによる影響が反映されない。

結局、基本はトポロジカル順に操作していって、 $b_j = i$ である $j$ について $a_j$ が負なら $j$ を $i$ より後ろへ後回しにすればいい。ただし、各操作における $a$ の変化をシミュレートしながらこの判断をする必要がある。

計算量は僕の実装だとたぶん $O(n \log n)$ 。

提出コード

リンク： http://codeforces.com/contest/1388/submission/88515835

using Graph = vector<Vi>;
 
bool topological_sort(std::vector<int>& res, const Graph& g) {
    const int n = static_cast<int>(g.size());
    res.resize(n);
    int idx = 0;
 
    int e = 0;
    std::vector<int> indeg(n);
    for (const auto& ch : g) {
        for (const auto& to : ch) {
            ++indeg[to];
            ++e;
        }
    }
 
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {
        if (indeg[i] == 0) st.push(i);
    }
 
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        res[idx++] = u;
        for (const auto& to : g[u]) {
            --indeg[to];
            --e;
            if (indeg[to] == 0) st.push(to);
        }
    }
 
    if (e > 0) {
        res.clear();
        return false;
    }
 
    return true;
}
 
void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    Graph g(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < N; i++) {
        int u;
        cin >> u;
        if (u == -1) continue;
        --u;
        g[i].emplace_back(u);
    }
    Vi topo;
    topological_sort(topo, g);
    vector<vector<Pll>> avals(N);
    ll v_ans = 0;
    Vi o_ans;
    for (auto u : topo) {
        sort(avals[u].begin(), avals[u].end(), greater<Pll>());
        ll sz = (ll)avals[u].size();
        ll t = A[u];
        for (ll i = 0; i < sz; i++) {
            if (avals[u][i].first < 0) break;
            t += avals[u][i].first;
            o_ans.emplace_back(avals[u][i].second);
        }
        v_ans += t;
        for (auto v : g[u]) {
            avals[v].emplace_back(t, u);
        }
    }
    vector<bool> used(N);
    for (auto u : o_ans) {
        used[u] = true;
    }
    reverse(topo.begin(), topo.end());
    for (auto u : topo) {
        if (!used[u]) {
            o_ans.emplace_back(u);
        }
    }
 
    prints()(v_ans);
    for (ll i = 0; i < N; i++) {
        cout << o_ans[i] + 1 << " ";
    }
    cout << "\n";
}