ABC 413

Sat, Jul 5, 2025

A. Content Too Large

https://atcoder.jp/contests/abc413/tasks/abc413_a

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

    int N, M;
    cin >> N >> M;
    ll sum = 0;
    rep(i, N) {
        int a;
        cin >> a;
        sum += a;
    }
    yesno(sum <= M);
}

B. cat 2

https://atcoder.jp/contests/abc413/tasks/abc413_b

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

    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];

    set<string> memo;
    rep(i, N) rep(j, N) {
        if (i == j) continue;
        memo.insert(S[i] + S[j]);
    }
    cout << memo.size() << endl;
}

C. Large Queue

https://atcoder.jp/contests/abc413/tasks/abc413_c

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

    int Q;
    cin >> Q;

    // cnt, num
    deque<pair<ll, ll>> deq;
    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            ll c, x;
            cin >> c >> x;
            deq.push_back({c, x});
        } else {
            ll sum = 0;
            ll k;
            cin >> k;
            while (k) {
                auto [c, x] = deq.front();
                deq.pop_front();
                if (k >= c) {
                    sum += c * x;
                    k -= c;
                } else {  // k < c
                    sum += k * x;
                    c -= k;
                    k = 0;
                    deq.push_front({c, x});
                }
            }
            cout << sum << endl;
        }
    }
}

D. Make Geometric Sequence

https://atcoder.jp/contests/abc413/tasks/abc413_d

自力 AC.

$N \leq 2$ のとき、常に Yes になる。

$N \geq 3$ のときを考える。

$r = 1$ となるとき、全ての数字が同じである必要がある。

$r = -1$ のとき、ある整数 $x$ が存在して、$x$ と $-x$ が交互に現れる必要がある。$x$ の個数と $-x$ の個数の差の絶対値が $1$ 以下である必要があるとき、等比数列を構築できる。

$|r| \neq 1$ のとき

数列 $A$ を $A_i$ の絶対値で昇順にソートしたものが等比数列になっている必要がある。(降順ソートでもよい) ソート後の数列に対して $r = A_i / A_{i-1} = A_{i+1} / A_i \Leftrightarrow A_i^2 = A_{i-1} A_{i+1}$ が成り立つとき、並べ替えによって等比数列が構築できる。それ以外のときは等比数列を構築できない。

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

    auto cal = []() -> void {
        int N;
        cin >> N;
        vll A(N);
        rep(i, N) cin >> A[i];
        vector<pair<ll, ll>> ps;
        rep(i, N) {
            ps.push_back({abs(A[i]), A[i]});
        }
        sort(all(ps));

        if (N <= 2) {
            Yes();
            return;
        }

        {
            int m = 0, p = 0;
            set<ll> stock;

            for (auto [a, x] : ps) {
                stock.insert(a);
                if (x < 0)
                    m++;
                else
                    p++;
            }

            if (stock.size() == 1) {
                if (min(m, p) == N / 2 || max(m, p) == N) {
                    Yes();
                    return;
                }
            }
        }

        bool ok = true;
        rep2(i, 1, N - 1) {
            ll y = ps[i].second;
            ll x = ps[i - 1].second;
            ll z = ps[i + 1].second;
            if (y * y != x * z) ok = false;
        }
        yesno(ok);
    };

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

E. Reverse 2^i

https://atcoder.jp/contests/abc413/tasks/abc413_e

自力 AC.

merge sort で merge するときに要素ごとに比較するのではなく、区間レベルで比較して merge していけばよい。

$M = 2^N$ とする。

反転させることのできる区間は以下の通りである。

$[0, M)$
$[0, \frac{M}{2})$, $[\frac{M}{2}, M)$
$[0, \frac{M}{4})$, $[\frac{4}{M}, \frac{2M}{4})$, $[\frac{2M}{4}, \frac{3M}{4})$, $[\frac{3M}{4}, M)$
…
$[0, \frac{M}{2^{N}})$, $[\frac{M}{2^{N}}, \frac{2M}{2^{N}})$, …, $[\frac{(2^{N}-1)M}{2^N}, M)$

$f(l,r)$ を区間 $[l, r)$ に対しての要素に対して反転させる操作を何回かして(0回でもよい)、辞書順で最小になる並べ方とする。

このとき、

\begin{align*} f(l,r) = \begin{cases} f(l, \floor{\frac{l+r}{2}}) + f(\floor{\frac{l+r}{2}}, r) \text{ if } f(l, \floor{\frac{l+r}{2}}) < f(\floor{\frac{l+r}{2}}, r) \\ f(\floor{\frac{l+r}{2}}, r) + f(l, \floor{\frac{l+r}{2}}) \text{ otherwise} \\ \end{cases} \end{align*}

とすることで辞書順最小の数列を構築できる。

答えは $f(0, 2^N)$ を出力する。

例 2 3 4 1 について考える。

$[0, 2)$ の区間対しては反転させる必要ない。
$[2, 4)$ の区間に対しては反転させる必要がある。よって 2 3 1 4 となる。
$[2, 3] < [1, 4]$ なので [1, 4] + [2, 3] = [1, 4, 2, 3] とする。

$[0, 2), [2, 4)$ の区間を交換するにはそれぞれの区間を逆転させた後に $[0, 4)$ の区間を逆転させればいい。

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

    auto f = [](auto f, vint& v, int l, int r) -> void {
        if (r - l == 1) {
            return;
        }

        int m = (l + r) / 2;
        f(f, v, l, m);
        f(f, v, m, r);
        vint t;
        if (v[l] > v[m]) {
            rep2(i, l, m) {
                swap(v[i], v[m + i - l]);
            }
        }
    };

    auto cal = [&]() -> void {
        ll N;
        cin >> N;
        vint P(1ll << N);
        rep(i, 1ll << N) cin >> P[i];
        f(f, P, 0, 1 << N);
        print(P);
    };

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

F. No Passage

https://atcoder.jp/contests/abc413/tasks/abc413_f

自力 AC.

4近傍にあるマスのうち、距離が確定しているマスの値の2番目に小さい値がそのマスの距離になる。 1番目に小さい値は青木くんに阻まれるので2番目に良い値を採用していく。

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

    int H, W, K;
    cin >> H >> W >> K;

    vll R, C;
    rep(i, K) {
        int r, c;
        cin >> r >> c;
        R.push_back(r);
        C.push_back(c);
    }

    vvll grid(H + 2, vll(W + 2, -1));
    rep(i, K) grid[R[i]][C[i]] = 0;

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    vvint cnt(H + 2, vint(W + 2));
    deque<pair<ll, ll>> deq;
    rep(i, K) deq.emplace_back(R[i], C[i]);
    while (deq.size()) {
        auto [r, c] = deq.front();
        deq.pop_front();
        rep(d, 4) {
            int ni = r + di[d], nj = c + dj[d];
            if (grid[ni][nj] >= 0) continue;
            cnt[ni][nj]++;
            if (cnt[ni][nj] == 2) {
                grid[ni][nj] = grid[r][c] + 1;
                deq.push_back({ni, nj});
            }
        }
    }

    ll ans = 0;
    rep2(i, 1, H + 1) rep2(j, 1, W + 1) {
        if (grid[i][j] > 0) ans += grid[i][j];
    }
    cout << ans << endl;
}

G. Big Banned Grid

https://atcoder.jp/contests/abc413/tasks/abc413_g

自力 AC.

8近傍にある障害物を連結して以下のいずれかのパスが存在するとき $(1, 1)$ から $(H, W)$ に到達できない。

上辺から下辺に達するパスが存在する
上辺から左辺に達するパスが存在する
右辺から下辺に達するパスが存在する
右辺から左辺に達するパスが存在する

まとめると「左辺または下辺」から「右辺または上辺」に達するパスが存在するか判定すればよい。

union find を使ってこれらのパスが存在するかを判定する。

この条件に気づいていれば F よりも G のほうが簡単に解けたからコンテスト中は F よりも G に取り組むべきだった。

模範解答によると最大流を踏まえた問題だったらしい。

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

    ll H, W, K;
    cin >> H >> W >> K;
    vll R(K), C(K);
    rep(i, K) {
        cin >> R[i] >> C[i];
    }

    using P = pair<int, int>;
    map<P, int> mp;
    rep(i, K) {
        mp[{R[i], C[i]}] = i + 1;
    }

    dsu uf(K + 2);
    rep(i, K) {
        int r = R[i], c = C[i];
        P p = {r, c};
        int id = mp[p];

        // 上辺、右辺の id は 0 とする
        if (r == 1) uf.merge(id, 0);
        if (c == W) uf.merge(id, 0);

        // 左辺、下辺の id は K+1 とする
        if (c == 1) uf.merge(id, K + 1);
        if (r == H) uf.merge(id, K + 1);
    }

    rep(i, K) {
        ll r = R[i], c = C[i];
        ll now = mp[{r, c}];
        for (int rd = -1; rd <= 1; rd++) {
            for (int cd = -1; cd <= 1; cd++) {
                ll nr = r + rd, nc = c + cd;
                if (!mp.count({nr, nc})) continue;
                ll nx = mp[{nr, nc}];
                uf.merge(now, nx);
            }
        }
    }

    bool ans = !uf.same(0, K + 1);
    yesno(ans);
}

ABC 413

Table of Contents

A. Content Too Large

B. cat 2

C. Large Queue

D. Make Geometric Sequence

E. Reverse 2^i

F. No Passage

G. Big Banned Grid