ABC 440

Sat, Jan 10, 2026

A. Octave

https://atcoder.jp/contests/abc440/tasks/abc440_a

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

    ll X, Y;
    cin >> X >> Y;

    cout << X * (1ll << Y) << endl;
}

B. Trifecta

https://atcoder.jp/contests/abc440/tasks/abc440_b

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

    ll N;
    cin >> N;
    vector<pair<ll, ll>> times;
    rep(i, N) {
        ll t;
        cin >> t;
        times.push_back({t, i + 1});
    }
    sort(all(times));

    vll ans;
    rep(i, 3) {
        ans.push_back(times[i].second);
    }
    print(ans);
}

C. Striped Horse

https://atcoder.jp/contests/abc440/tasks/abc440_c

コンテスト中には解けなかったが自力で解けた。

周期 $2W$ ごとに $W$ 個のコストを足す区間と、$W$ 個のコストを飛ばす区間が交互に現れる。ここで区間は右開区間として考える。採用する区間のうち一番左にある区間の右端の位置を $r$ とすると $[r-W, r)$, $[r+W, r+2W)$, … の区間を採用することになる。ここで $r \in [1, 2W]$ である。

$r$ の取り方が $2W$ 通りしかないので、loop の回数は $\frac{N}{2W}$ であるので累積和を計算しておけば $O(N)$ で解ける。

下記のコードは簡単のために $C$ の長さを $N + 2W$ に拡張しているので計算量は $O(N+W)$ である。

template <typename T>
struct Cumsum {
    vector<T> data;

    Cumsum(vector<T> v) {
        int n = v.size();
        data.resize(n + 1);

        data[0] = 1;
        rep(i, n) {
            data[i + 1] = data[i] + v[i];
        }
    }

    // sum of range [l,r)
    ll sum(int l, int r) {
        return data[r] - data[l];
    }
};

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

    auto cal = []() -> void {
        ll N, W;
        cin >> N >> W;
        vll C(N + W * 2);
        rep(i, N) cin >> C[i];
        N += W * 2;

        Cumsum cm(C);

        ll ans = INF;
        rep2(fin, 1, W * 2 + 1) {
            ll tmp = 0;
            for (ll r = fin; r < N; r += W * 2) {
                tmp += cm.sum(max(0ll, r - W), r);
            }
            chmin(ans, tmp);
        }
        cout << ans << endl;
    };

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

解説放送で知ったやり方。 $2W$ 離れたところは一蓮托生なので $2W$ 個の要素の配列から $W$ 個の連続する要素を選ぶ問題に帰着できる。

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

    auto cal = []() -> void {
        ll N, W;
        cin >> N >> W;
        vll C(W * 4);
        rep(i, N) {
            ll c;
            cin >> c;
            C[i % (W * 2)] += c;
            C[i % (W * 2) + W * 2] += c;
        }

        ll ans = accumulate(C.begin(), C.begin() + W, 0ll);
        ll sum = ans;
        rep2(i, 1, W * 2 + 1) {
            sum -= C[i - 1];
            sum += C[i + W - 1];
            chmin(ans, sum);
        }
        cout << ans << endl;
    };

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

D. Forbidden List 2

https://atcoder.jp/contests/abc440/tasks/abc440_d

コンテスト中には解けなかったが自力で解けた。

$x \geq X_j$ とする。$[X_j, x]$ の区間に含まれる $A_i$ の個数を $n$ とすると $x$ は $X_j$ から $A$ に含まれない数の $x - X_j + 1 - n$ 番目の数である。

$x$ を二分探索で動かして $Y_j$ 番目の数を求めればよい。

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

    ll N, Q;
    cin >> N >> Q;

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

    rep(i, Q) {
        ll x, y;
        cin >> x >> y;
        auto lit = lower_bound(all(A), x);

        ll ac = 1ll << 60, wa = x - 1;
        while (ac - wa > 1) {
            ll wj = (ac + wa) / 2;
            auto rit = upper_bound(lit, A.end(), wj);
            ll num = rit - lit;
            if (wj - x + 1 - num < y) {
                wa = wj;
            } else {
                ac = wj;
            }
        }
        cout << ac << endl;
    }
}

E. Cookies

https://atcoder.jp/contests/abc440/tasks/abc440_e

F. Egoism

https://atcoder.jp/contests/abc440/tasks/abc440_f

G. Haunted House

https://atcoder.jp/contests/abc440/tasks/abc440_g