ABC 288

Sat, Jan 24, 2026

https://atcoder.jp/contests/abc288

A. Many A+B Problems

https://atcoder.jp/contests/abc288/tasks/abc288_a

B. Qualification Contest

https://atcoder.jp/contests/abc288/tasks/abc288_b

C. Don’t be cycle

https://atcoder.jp/contests/abc288/tasks/abc288_c

D. Range Add Query

https://atcoder.jp/contests/abc288/tasks/abc288_d

2026/1/24 解説 AC

あまりでまとめる系の問題だということを知った状態で解いたが自力では解けなかった。

https://kenkoooo.com/atcoder/#/contest/show/bd593eb7-d83c-479e-a99d-d6242eff88ea?activeTab=Problems

$(X_1, X_2, \cdots, X_n)$ に対して先頭から $0$ にしていくことを考える。最初の $K$ 個の要素 $(X_1, X_2, \cdots, X_K)$ を $0$ にするには、各要素に $-X_i$ 加算すれば良い。次に $(X_{i+1}, X_{i+2}, \cdots, X_{i+K})$ を $0$ にするには、各要素を $X_i - X_{i+1}$ 加算すれば良い。これを繰り返していってすべての要素を $0$ にできれば良い数列であるがこれを愚直に実装すると TLE する。

ここで操作をするごとに数字がどのように変わるのかに注目する。

先程同様 $X_1$ を $0$ にするためにはじめの $K$ 個の要素に $-X_1$ 加算する。次に2番目の要素を $0$ にするために、まず1番目の要素を 0 にするために加算された $-X_1$ を打ち消すために $i \in [2,K+2)$ 番目の要素に $X_1$ を加算する。こうするとこの時点での数列はもとの数列の1番目の要素が $0$ に、$K+1$ 番目の要素に $X_1$ が加算された数列になる。

よって操作をするごとに要素を $K$ 個先に送ることができる。これより $i \mod K$ ごとにグループ分けして独立して考えることができる。

$\displaystyle S_r = \sum_{i \equiv r \mod K} A_i$ とすると最終的な答えは $S_0 = S_1 = \cdots = S_{K-1}$ であるかどうかで判定できる。

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];

    vvll cm(K, vll(N + 1));
    rep(i, N) {
        cm[i % K][i + 1] = A[i];
    }
    rep(i, K) rep(j, N) {
        cm[i][j + 1] += cm[i][j];
    }

    ll Q;
    cin >> Q;
    while (Q--) {
        ll l, r;
        cin >> l >> r;
        l--;

        vll s;
        rep(i, K) {
            s.push_back(cm[i][r] - cm[i][l]);
        }
        sort(all(s));
        yesno(s[0] == s.back());
    }
}