ABC 341

Table of Contents

D - Only one of two

https://atcoder.jp/contests/abc341/tasks/abc341_d

解説 AC

$x$ 以下の整数のうち $N$, $M$ のいずれか一方のみで割り切れるものの個数を $f(x)$ とすると

\begin{align*} f(x) = \floor{\frac{x}{N}} + \floor{\frac{x}{M}} - 2 \cdot \floor{\frac{x}{\text{lcm}(N, M)}} \end{align*}

である。

$f(x) \geq K$ となる最小の $x$ を二分探索で求めれば良い。

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

    ll N, M, K;
    cin >> N >> M >> K;

    auto f = [&](ll x) -> ll {
        ll numn = x / N;
        ll numm = x / M;
        ll numc = x / lcm(N, M);

        return numn + numm - numc * 2;
    };

    ll wa = 0, ac = INF;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj) >= K)
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

E - Alternating String

https://atcoder.jp/contests/abc341/tasks/abc341_e

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

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

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

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

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

    auto e = []() -> ll {
        return 0;
    };

    ll m = (ll)6e5 + 5;
    segtree<ll, op, e> seg(m);

    for (ll a : A) {
        ll l = max(0ll, a - K);
        ll r = a + K + 1;
        seg.set(a, seg.prod(l, r) + 1);
    }

    cout << seg.all_prod() << endl;
}