ABC 409

Table of Contents

https://atcoder.jp/contests/abc409

5完で水色パフォーマンスが出たがボンミスや、問題文の誤読などで4ペナもしてしまった。

A - Conflict

https://atcoder.jp/contests/abc409/tasks/abc409_a

S[i] == T[i] かだけ調べて o か否かを調べないせいでペナを食らった。

B - Citation

https://atcoder.jp/contests/abc409/tasks/abc409_b

$A$ に含まれている要素が答えになると思ったが全部が $10^9$ のとき $x = N$ が答えとなるがそのへんのことが全然考えられていなかった。

$N \leq 100$ で、$A$ に現れるのが $x$ 回以上と言われれば $x \leq N$ となるのは当たり前過ぎたのにそのへんがわかってなくて2ペナもしてしまった。

C - Equilateral Triangle

https://atcoder.jp/contests/abc409/tasks/abc409_c

正三角形になるためには $ab$ 間, $bc$ 間, $ca$ 間の距離が等しくなければならず、間隔は $\frac{L}{3}$ である。 $d_i$ が整数なので $L$ が3の倍数でなければ条件と満たすような $a, b, c$ は存在しない。

問題文では点を打つことになっているが該当箇所にコマを置くと考える。 円周を $L$ 分割して 0 から $L-1$ まで点を打つ。$L-1$ の次は 0 に戻る。 $i$ にあるコマの数を $C_i$ とすると求める正三角形の数は

\begin{align*} \sum_{i=0}^{L/3-1} C_i \cdot C_{(i + L/3) \mod L} \cdot C_{(i + 2L/3) \mod L} \end{align*}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, L;
    cin >> N >> L;
    vll D(N - 1);
    rep(i, N - 1) cin >> D[i];

    if (L % 3 != 0) {
        cout << 0 << endl;
        return;
    }

    vll cnts(L);
    cnts[0] = 1;
    int p = 0;
    rep(i, N - 1) {
        ll nx = (p + D[i]) % L;
        cnts[nx]++;
        p = nx;
    }

    ll ans = 0;
    ll width = L / 3;
    rep(i, L / 3) {
        ll a = i;
        ll b = (i + width) % L;
        ll c = (i + width * 2) % L;

        ans += cnts[a] * cnts[b] * cnts[c];
    }
    cout << ans << endl;
}

D - String Rotation

https://atcoder.jp/contests/abc409/tasks/abc409_d

fin の計算で break を入れ忘れてペナを食らった。

$S_i > S_{i+1}$ となる部分があれば、$S_i$ を $i+1$ 以降に挿入することで $S$ の辞書順を小さくできる。 このとき、$S_i > S_{i+1}$ となる $i$ のうち最小のものを交換したほうが辞書順でより小さくできる。 $S_i > S_{i+1}$ となる $i$ がなければ $S$ はすでに辞書順で最小なのでそのまま出力する。

$S_i > S_{i+1}$ となる最小の $i$ を start とする. $S_{\mathrm{start}}$ の挿入場所は $i+1$ 番目以降のうち $S_{\mathrm{start}} < S_j$ を満たす 最小の $j$ の前を選ぶのが最適である。 そのような $j$ がなければ $S_{\mathrm{start}}$ を末尾に挿入する。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N;
        string S;
        cin >> N >> S;

        int start = -1;
        rep(i, N - 1) {
            if (S[i] > S[i + 1]) {
                start = i;
                break;
            }
        }
        if (start == -1) {
            cout << S << endl;
            return;
        }

        int fin = -1;
        rep2(i, start + 1, N) {
            if (S[start] < S[i]) {
                fin = i;
                break;
            }
        }

        if (fin == -1) {
            S.push_back(S[start]);
        } else {
            string t = "";
            t.push_back(S[start]);
            S.insert(fin, t);
        }

        S.erase(start, 1);
        cout << S << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

E - Pair Annihilation

https://atcoder.jp/contests/abc409/tasks/abc409_e

考えたこと

粒子の動かす方向に限らず辺 $j$ を通るときの粒子の数を $C_j$ とすると $C_j \times w_j$ のエネルギーが消費される。 木の内側にある粒子よりも葉側の粒子を内側に寄せていくことを考えると簡単そう。 適当に根を決めて DFS して葉から親の方へ向かって粒子を寄せていけば良さそう。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll X(N);
    rep(i, N) cin >> X[i];

    using P = pair<ll, ll>;
    vector<vector<P>> graph(N);
    rep(i, N - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    ll ans = 0;
    auto dfs = [&](auto dfs, int now, int p = -1) -> ll {
        ll sum = X[now];

        // 隣の頂点からいくつの電荷がくるか計算
        for (auto [nx, w] : graph[now]) {
            if (nx == p) continue;

            ll m = dfs(dfs, nx, now);
            ans += abs(m) * w;
            sum += m;
        }

        return sum;
    };

    dfs(dfs, 0);
    cout << ans << endl;
}

F - Connecting Points

コンテスト後に自力 AC.

考えたこと

TLE 解法

頂点間の距離 $k$ を key, 距離が $k$ となる頂点の組の集合を値とした map を用意する。 連結判定は union find で用いて行う。 連結成分数を別途管理しておく。初期値は $N$.

type 1 のクエリでは既存の頂点と新たに追加された頂点との距離を計算して map に追加する。 連結成分数を 1 増やす。

type 2 では、map のうち最小の key を取り出して、その中の値に含まれる頂点の組についてまだ連結していないものがあればその key を出力。連結していない組があるたびに連結成分数を 1 減らす。 組が全て連結成分であればその次の key について同様に調べる。調べた key 全てについて map からその key を削除。

type 3 では union find で連結かどうかを判定。

という風に実装したら TLE した。どうやら map が思いっぽい。

解法

距離に関して昇順に出てくるように priority queue を用いて上記と同様のことを行うと AC する。

解説放送の実装だと連結成分が 1 か否かを priority queue の size が 0 かどうかで判定していてより洗練されている。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    vector<pair<ll, ll>> pos;
    rep(i, N) {
        ll x, y;
        cin >> x >> y;
        pos.emplace_back(x, y);
    }

    // dist, x, y
    using T = tuple<ll, ll, ll>;
    priority_queue<T, vector<T>, greater<T>> pq;

    rep(i, N) rep2(j, i + 1, N) {
        ll d = abs(pos[i].first - pos[j].first) + abs(pos[i].second - pos[j].second);
        pq.push({d, i, j});
    }

    dsu uf(N + Q);
    int nc = N;

    rep(_, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            ll a, b;
            cin >> a >> b;
            rep(i, N) {
                auto [x, y] = pos[i];
                ll d = abs(x - a) + abs(y - b);
                pq.push({d, i, N});
            }
            N++;
            nc++;
            pos.emplace_back(a, b);
        } else if (t == 2) {
            if (nc == 1) {
                cout << -1 << endl;
                continue;
            }

            ll k = -1;
            while (pq.size()) {
                auto [d, u, v] = pq.top();
                pq.pop();
                if (uf.same(u, v)) continue;
                if (d > k && k >= 0) {
                    pq.push({d, u, v});
                    break;
                }
                uf.merge(u, v);
                nc--;
                if (k < 0)
                    k = d;
            }
            cout << k << endl;

        } else {
            int u, v;
            cin >> u >> v;
            u--, v--;
            yesno(uf.same(u, v));
        }
    }
}