ABC 439

Sun, Jan 4, 2026

A. 2^n - 2*n

https://atcoder.jp/contests/abc439/tasks/abc439_a

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

    ll N;
    cin >> N;
    cout << (1ll << N) - (N * 2) << endl;
}

B. Happy Number

https://atcoder.jp/contests/abc439/tasks/abc439_b

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

    ll N;
    cin >> N;

    set<ll> memo;
    while (N != 1) {
        ll sum = 0;
        while (N) {
            ll m = N % 10;
            sum += m * m;
            N /= 10;
        }

        if (memo.count(sum)) {
            No();
            return;
        }
        memo.insert(sum);
        N = sum;
    }

    Yes();
}

C. 2026

https://atcoder.jp/contests/abc439/tasks/abc439_c

$x \leq \sqrt{N}$, $y \leq \sqrt{N}$ であるので $(x,y)$ の全探索を行っても $O(N)$ で解ける。

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

    ll N;
    cin >> N;

    vll used(N + 1);

    for (int i = 1; i * i <= N; i++) {
        for (int j = i + 1; j * j <= N; j++) {
            ll sq = i * i + j * j;
            if (sq > N) continue;
            used[sq]++;
        }
    }

    vll ans;
    rep(i, N + 1) {
        if (used[i] == 1) ans.push_back(i);
    }
    cout << ans.size() << endl;
    print(ans);
}

D. Kadomatsu Subsequence

https://atcoder.jp/contests/abc439/tasks/abc439_d

$A_i : A_j : A_k = 7 : 5 : 3$ であるから

$A_i = \frac{7 A_j}{5}$, $A_k = \frac{3 A_j}{5}$ がともに整数にならなければならないので $A_j$ は 5 の倍数である必要がある。 $A_j$ が決まれば $A_i, A_k$ も一意に決まるので、あとは条件を満たす $i, k$ の個数を数え上げればよい。

特定の $j$ について、$\min(i,j,k) = j \wedge A_i : A_j : A_k = 7 : 5 : 3$ を満たす組の個数は $i < j$ かつ $A_i = \frac{7 A_j}{5}$ であるような $i$ の個数と $k < j$ かつ $A_k = \frac{3 A_j}{5}$ であるような $k$ の個数の積になる。

同様にして $\max(i,j,k) = j \wedge A_i : A_j : A_k = 7 : 5 : 3$ を満たす組の個数は $i > j$ かつ $A_i = \frac{7 A_j}{5}$ であるような $i$ の個数と $k > j$ かつ $A_k = \frac{3 A_j}{5}$ であるような $k$ の個数の積になる。

これらの和が答えになる。

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

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

    map<ll, vll> mp;
    rep(i, N) {
        mp[A[i]].push_back(i);
    }

    ll ans = 0;
    for (int j = N - 1; j >= 0; j--) {
        if (A[j] % 5 != 0) continue;

        ll lx = A[j] / 5 * 7;
        ll rx = A[j] / 5 * 3;

        ll numl = lower_bound(all(mp[lx]), j) - mp[lx].begin();
        ll numr = lower_bound(all(mp[rx]), j) - mp[rx].begin();

        ans += numl * numr;
    }

    rep(j, N) {
        if (A[j] % 5 != 0) continue;

        ll lx = A[j] / 5 * 7;
        ll rx = A[j] / 5 * 3;

        ll numl = mp[lx].end() - lower_bound(all(mp[lx]), j);
        ll numr = mp[rx].end() - lower_bound(all(mp[rx]), j);

        ans += numl * numr;
    }
    cout << ans << endl;
}

E. Kite

https://atcoder.jp/contests/abc439/tasks/abc439_e

解説 AC

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] >> B[i];

    using P = pair<ll, ll>;
    vector<P> ps;
    rep(i, N) {
        ps.emplace_back(A[i], B[i]);
    }

    sort(all(ps), [](P a, P b) -> bool {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    vll v(N, INF);

    rep(i, N) {
        auto [_, b] = ps[i];
        auto it = lower_bound(all(v), b);
        *it = b;
    }

    ll ans = 0;
    rep(i, N) {
        if (v[i] != INF) ans++;
    }
    cout << ans << endl;
}

F. Beautiful Kadomatsu

https://atcoder.jp/contests/abc439/tasks/abc439_f

G. Sugoroku 6

https://atcoder.jp/contests/abc439/tasks/abc439_g