Codeforces Round #668 (Div. 2) 感想

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

ABCDの4完でレート変動は 1864→1905 (+41)。

わーい！紫になったぞ！（3回目）。......もはや達成感とかは何もない。

A - Permutation Forgery

これはギャグで、 reverse すればok。

提出コード

リンク： http://codeforces.com/contest/1405/submission/92024710

inline void solve_one() {
    ll N;
    cin >> N;
    Vi A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    reverse(A.begin(), A.end());
    for (ll i = 0; i < N; i++) {
        prints("", " ")(A[i]);
    }
    prints()();
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

「 $a_i \gt 0$ かつ $a_j \lt 0$ 」を満たさない $(i, j)$ に対して操作を行っても無駄なので、操作を行うのはこの条件を満たす $(i, j)$ のみに限る。このとき、操作回数は操作列にかかわらず $\frac{1}{2} \sum_{i = 1}^{n} |a_i|$ となる。なので、コストのかからない操作回数を最大化することを考えればいい。これは、先にコストのかからない操作をできるだけやってしまうことで達成できる。

提出コード

リンク： http://codeforces.com/contest/1405/submission/92033061

inline void solve_one() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    reverse(A.begin(), A.end());
    ll cur = 0;
    for (ll i = 0; i < N; i++) {
        if (A[i] < 0) {
            cur += -A[i];
            A[i] = 0;
        }
        else if (A[i] > 0) {
            ll t = min(cur, A[i]);
            cur -= t;
            A[i] -= t;
        }
    }
 
    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += A[i];
    }
    prints()(ans);
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

C - Balanced Bitstring

この問題ではダメムーブをしてしまった。考察がまとまる前に実装してしまい、書いては消し、書いては消しを繰り返して時間を浪費してしまった。

「 $a[ 1 \ldots k ]$ を $k$ -balanced にできる」かつ「 $a$ を周期 $k$ にできる」ならば YES、そうでなければ NO。

......なんだけど、提出したコードでは $a[ i \ldots i + k - 1 ]\ (\forall i \in \{ 1, \ldots , n - k + 1 \})$ を $k$ -balanced にできるかを確かめていて、無駄を含む実装となっている。ダメムーブはコードもダメにするね。

提出コード

リンク： http://codeforces.com/contest/1405/submission/92050153

inline void solve_one() {
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    bool ok = true;
    for (ll i = 0; i < K; i++) {
        int f = -1;
        for (ll j = i; j < N; j += K) {
            if (f == -1) {
                if (S[j] == '0') {
                    f = 0;
                }
                else if (S[j] == '1') {
                    f = 1;
                }
            }
            else {
                if (S[j] == '0' && f == 1) {
                    ok = false;
                }
                else if (S[j] == '1' && f == 0) {
                    ok = false;
                }
            }
        }
        if (f != -1) {
            for (ll j = i; j < N; j += K) {
                if (f == 0) {
                    S[j] = '0';
                }
                else {
                    S[j] = '1';
                }
            }
        }
    }
 
    ll n0 = 0, n1 = 0, nq = 0;
    for (ll i = 0; i < K; i++) {
        if (S[i] == '0') {
            ++n0;
        }
        else if (S[i] == '1') {
            ++n1;
        }
        else {
            ++nq;
        }
    }
    {
        ll d0 = K / 2 - n0;
        ll d1 = K / 2 - n1;
        if (d0 < 0 || d1 < 0 || d0 + d1 != nq) {
            ok = false;
        }
    }
 
    for (ll i = K; i < N; i++) {
        if (S[i - K] == '0') {
            --n0;
        }
        else if (S[i - K] == '1') {
            --n1;
        }
        else {
            --nq;
        }
        if (S[i] == '0') {
            ++n0;
        }
        else if (S[i] == '1') {
            ++n1;
        }
        else {
            ++nq;
        }
        ll d0 = K / 2 - n0;
        ll d1 = K / 2 - n1;
        if (d0 < 0 || d1 < 0 || d0 + d1 != nq) {
            ok = false;
        }
    }
 
    prints()(ok ? "YES" : "NO");
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

コンテスト後提出コード

リンク： http://codeforces.com/contest/1405/submission/92077917

inline void solve_one() {
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    bool ok = true;
    for (ll i = 0; i < K; i++) {
        int f = -1;
        for (ll j = i; j < N; j += K) {
            if (f == -1) {
                if (S[j] == '0') {
                    f = 0;
                }
                else if (S[j] == '1') {
                    f = 1;
                }
            }
            else {
                if (S[j] == '0' && f == 1) {
                    ok = false;
                }
                else if (S[j] == '1' && f == 0) {
                    ok = false;
                }
            }
        }
        if (f != -1) {
            for (ll j = i; j < N; j += K) {
                if (f == 0) {
                    S[j] = '0';
                }
                else {
                    S[j] = '1';
                }
            }
        }
    }
 
    ll n0 = 0, n1 = 0, nq = 0;
    for (ll i = 0; i < K; i++) {
        if (S[i] == '0') {
            ++n0;
        }
        else if (S[i] == '1') {
            ++n1;
        }
        else {
            ++nq;
        }
    }
    {
        ll d0 = K / 2 - n0;
        ll d1 = K / 2 - n1;
        if (d0 < 0 || d1 < 0 || d0 + d1 != nq) {
            ok = false;
        }
    }
 
    prints()(ok ? "YES" : "NO");
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

D - Tree Tag

$da, db$ っていう表記やめてほしい。 $d_a,\ d_b$ とかにすべきでしょ。

$a$ と $b$ の距離が $d_a$ 以下の場合は、初手で Alice が勝つ。以下、そうでないとき。

$d_b \le 2 d_a$ のとき、Alice は「Bob までの距離が $d_a$ より大きい場合は Bob のいる方向へ 1 つ移動し、そうでなければ Bob のところへ移動する」という行動を行うことで必ず勝つことができる。

$d_b \gt 2 d_a$ のときは Bob は木が十分に大きくて逃げ場があるときはいつまでも逃げ続けることができる。具体的には木の直径が $d_a$ より大きければ ok。

木の直径が $d_a$ 以下の場合は Alice が次の行動でどの頂点にも移動できるような頂点が存在するので無理。

提出コード

リンク： http://codeforces.com/contest/1405/submission/92064463

using Graph = vector<Vi>;
int depth[100010];
 
inline void solve_one() {
    ll N, a, b, da, db;
    cin >> N >> a >> b >> da >> db;
    --a, --b;
    Graph g(N);
    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);
    }
    if (db <= da * 2) {
        prints()("Alice");
        return;
    }
 
    auto dfs = [&](auto&& self, int idx, int par, int d) -> void {
        for (auto u : g[idx]) {
            if (u == par) continue;
            depth[u] = d + 1;
            self(self, u, idx, d + 1);
        }
    };
 
    depth[a] = 0;
    dfs(dfs, a, -1, 0);
    if (depth[b] <= da) {
        prints()("Alice");
        return;
    }
 
    ll x;
    {
        ll mx = 0;
        for (ll i = 0; i < N; i++) {
            if (chmax(mx, depth[i])) {
                x = i;
            }
        }
    }
 
    depth[x] = 0;
    dfs(dfs, x, -1, 0);
 
    ll r = 0;
    for (ll i = 0; i < N; i++) {
        chmax(r, depth[i]);
    }
 
    if (r > da * 2) {
        prints()("Bob");
    }
    else {
        prints()("Alice");
    }
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

E - Fixed Point Removal

クエリをソートしてセグ木とかでごにょごにょするのかな～～という雰囲気を感じた。感じただけなので解けなかった。

スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

Codeforces Round #668 (Div. 2) 感想

A - Permutation Forgery

B - Array Cancellation

C - Balanced Bitstring

D - Tree Tag

E - Fixed Point Removal