ABC 351

Tue, Jan 20, 2026

https://atcoder.jp/contests/abc351

A. The bottom of the ninth

https://atcoder.jp/contests/abc351/tasks/abc351_a

B. Spot the Difference

https://atcoder.jp/contests/abc351/tasks/abc351_b

C. Merge the balls

https://atcoder.jp/contests/abc351/tasks/abc351_c

D. Grid and Magnet

https://atcoder.jp/contests/abc351/tasks/abc351_d

3時間近くかかったが自力 AC

磁石が置かれていないマスを空マスと呼ぶことにする。磁石と隣接していない空マス同士を union-find で連結する。連結部分のサイズと連結部分の外縁にある磁石と隣接する空マスの数の合計のうち最大値を出力する。

int h, w;
vector<string> grid;
vvint memo;
vvint visited;
vint di = {0, 1, 0, -1};
vint dj = {1, 0, -1, 0};

pair<int, int> ind2sub(int x) {
    return {x / w, x % w};
}

int sub2ind(int i, int j) {
    return i * w + j;
}

int canMove(int i, int j) {
    int ok = 1;
    rep(d, 4) {
        int ni = i + di[d], nj = j + dj[d];
        if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
            continue;
        if (grid[ni][nj] == '#')
            ok = 0;
    }

    return ok;
}

void solve() {
    cin >> h >> w;
    grid = vector<string>(h);
    rep(i, h) cin >> grid[i];

    dsu uf(h * w);

    rep(i, h) rep(j, w) {
        if (grid[i][j] == '.' && canMove(i, j)) {
            for (auto [ii, jj] : vector<pair<int, int>>({{1, 0}, {0, 1}})) {
                int ni = i + ii, nj = j + jj;
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (canMove(ni, nj)) {
                    uf.merge(sub2ind(i, j), sub2ind(ni, nj));
                }
            }
        }
    }

    int ans = 1;
    for (auto v : uf.groups()) {
        set<pair<int, int>> stop;
        {
            auto [i, j] = ind2sub(v[0]);
            if (grid[i][j] == '#')
                continue;
            else if (!canMove(i, j)) {
                continue;
            }
        }
        for (int id : v) {
            auto [i, j] = ind2sub(id);
            rep(d, 4) {
                int ni = i + di[d], nj = j + dj[d];
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (grid[ni][nj] == '.' && !canMove(ni, nj))
                    stop.insert({ni, nj});
            }
        }
        chmax(ans, (int)v.size() + (int)stop.size());
    }

    cout << ans << endl;
}

E. Jump Distance Sum

https://atcoder.jp/contests/abc351/tasks/abc351_e

F. Double Sum

https://atcoder.jp/contests/abc351/tasks/abc351_f

2026/1/20 segment tree の問題だとわかった状態で自力 AC

https://kenkoooo.com/atcoder/#/contest/show/76c42792-10db-491b-9486-ffc7f4f226e1?activeTab=Standings

$i < j \wedge A_i \geq A_j$ のなる $(i,j)$ の組み合わせはすべて 0 になるので無視する。

$A_j$ を固定して考える。 $A_j$ よりも左にある $A_j$ よりも小さい数の個数を $n$ とし、 $A_j$ よりも左にある $A_j$ よりも小さい数のの和を $S$ とすると、 $A_j$ を右端とするような組み合わせの和は $n A_j - S$ になる。

これは (値, 個数) を segment tree で持ち、$A$ の大きい順に見ていき、見ている値を右端とする組み合わせを足し合わせていくことで求めることができる。計算をする毎にすでに見た値は segment tree 上で 0 にしていくことで、常に自分よりも小さい値の個数と和を取得できるようになる。このとき値が同じになる $A_i$ が複数ある場合、index の小さい方から見ていかないと正しい答えが求まらないことに注意する。

struct S {
    ll val, cnt;
};

S op(S a, S b) {
    return {a.val + b.val, a.cnt + b.cnt};
}

S e() {
    return {0, 0};
}

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

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    segtree<S, op, e> seg(N);
    rep(i, N) {
        seg.set(i, {A[i], 1});
    }

    // number, id
    using P = pair<ll, ll>;
    vector<P> ps;
    rep(i, N) ps.emplace_back(A[i], i);
    sort(all(ps), [](P a, P b) -> bool {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

    ll ans = 0;
    for (auto [x, id] : ps) {
        S now = seg.prod(0, id);
        ans += x * now.cnt - now.val;
        seg.set(id, {0, 0});
    }
    cout << ans << endl;
}

G. Hash on Tree

https://atcoder.jp/contests/abc351/tasks/abc351_g