ABC 368

Table of Contents

D - Minimum Steiner Tree

https://atcoder.jp/contests/abc368/tasks/abc368_d

$V_1$ から DFS して、子または自身が $V_i$ に含まれていればそのノードを残す。

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

    ll N, K;
    cin >> N >> K;
    vvint graph(N);
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    set<int> vs;
    rep(i, K) {
        int x;
        cin >> x;
        x--;
        vs.insert(x);
    }

    vint used(N);

    auto dfs = [&](auto dfs, int now, int p) -> int {
        int found = vs.count(now);
        for (int nx : graph[now]) {
            if (nx == p) continue;
            found = dfs(dfs, nx, now) || found;
        }

        return used[now] = found;
    };

    dfs(dfs, *vs.begin(), -1);

    cout << accumulate(all(used), 0ll) << endl;
}

F - Dividing Game

解説 AC

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

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

    int mx = 1e5 + 5;
    vll sieve(mx, 0);
    rep2(i, 2, mx) {
        for (int j = i; j < mx; j += i) {
            if (sieve[j] == 0)
                sieve[j] = i;
        }
    }

    auto factor_sum = [&](int x) -> int {
        int ans = 0;
        while (x != 1) {
            int d = sieve[x];
            while (x % d == 0) {
                ans++;
                x /= d;
            }
        }
        return ans;
    };

    vll nim;
    rep(i, N) {
        nim.push_back(factor_sum(A[i]));
    }

    ll sum = 0;
    for (ll x : nim)
        sum ^= x;
    string ans = "Anna";
    if (sum == 0) {
        ans = "Bruno";
    }
    cout << ans << endl;
}

G - Add and Multiply Queries

https://atcoder.jp/contests/abc368/tasks/abc368_g

2026/2/15 解説 AC

segment tree を使う問題とわかった状態でやったが解けなかった。

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

解説を読んで解き方はわかったが、これのどの部分を他の問題に取り組むときに応用できるのかがいまいちピンときていない。 答えが $10^{18}$ だから掛け算を選ぶべきところは高々 60 個程度というところが他の問題を解くときに使えるところかなぁ。

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

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

    auto opplus = [](ll a, ll b) -> ll {
        return a + b;
    };
    auto oppluse = []() -> ll {
        return 0;
    };

    auto opmax = [](ll a, ll b) -> ll {
        return max(a, b);
    };
    auto opmaxe = []() -> ll {
        return -1;
    };

    segtree<ll, opplus, oppluse> sega(A);
    segtree<ll, opmax, opmaxe> segb(B);

    ll Q;
    cin >> Q;
    while (Q--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll i, x;
            cin >> i >> x;
            i--;
            sega.set(i, x);
        } else if (t == 2) {
            ll i, x;
            cin >> i >> x;
            i--;
            segb.set(i, x);
        } else {
            ll l, r;
            cin >> l >> r;
            l--;

            auto f = [](ll x) -> bool {
                return x <= 1;
            };

            ll v = 0;

            while (l < r) {
                v = max(v + sega.get(l), v * segb.get(l));
                ll next_l = min(r, (ll)segb.max_right(l + 1, f));
                if (l + 1 < next_l)
                    v += sega.prod(l + 1, next_l);
                l = next_l;
            }
            cout << v << endl;
        }
    }
}