けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!!

問題へのリンク

問題概要

長さ  N の数列  X が与えられる。初期状態では  X の要素は全て 0 である。加えて、 M 個の整数のペア( A_i, B_i)が与えられる。各ペアに対し以下の操作を行い、最終的な数列  X を出力せよ。

  •  j に対し、 (A_i + j) B_i で割った余りを  X_j に加える。

制約

  •  1 \le N, M \le 10^{5}
  •  0 \le A_i <  B_i \le 10^{9}

考えたこと

三角波を重ね合わせるような問題。第一感、imos 法をしたくなる。差分をとってみると、

  • ほとんどの場所が +1
  • 端っこだけちょっと変
  • 周期 B ごとに -B

という感じになる。ほとんどの場所が +1 というのは別にカウントしておけばいいので、実質的に

  • 端っこが変
  • 周期 B ごとに -1-B

という操作になる。これは、B が十分大きければいいのだが...という気持ちになる。なので B が小さいときは別の集計方法があるのではないかと考えてみると、確かに平方分割的発想にいたるのかもしれない。

B が小さいときは、同じ B について重ね合わせてると、B ごとに加算を繰り返す感じになるので、B ごとにまとめてしまえばいい。そのような B が十分少ないことから実現できる。

最終的な計算量は  O((M + N)\sqrt{N})

#include <iostream>
#include <vector>
using namespace std;

const int DIV = 350;

int N, M;
vector<long long> A, B;

int main() {
    cin >> N >> M;
    A.resize(M); B.resize(M);
    for (int i = 0; i < M; ++i) scanf("%lld %lld", &A[i], &B[i]);

    vector<vector<long long> > sb(DIV, vector<long long>(DIV, 0));
    vector<long long> imos(N+1, 0);
    long long geta = 0;
    for (int i = 0; i < M; ++i) {
        if (B[i] < DIV) {
            for (int j = 0; j < B[i]; ++j) {
                long long q = (A[i] + j + 1) % B[i];
                sb[B[i]][j] += q;
            }
        }
        else {
            ++geta;
            imos[0] += A[i];
            imos[N] += -1 - (A[i]+N)%B[i];
            for (int q = B[i]-A[i]-1; q < N; q += B[i]) {
                imos[q] -= B[i];
            }
        }
    }
    for (int i = 0; i <= N; ++i) imos[i] += geta;
    for (int i = 0; i <= N; ++i) imos[i+1] += imos[i];
    
    vector<long long> res = imos;
    for (int b = 1; b < DIV; ++b) {
        for (int i = 0; i < N; ++i) {
            int r = i % b;
            res[i] += sb[b][r];
        }
    }
    
    for (int i = 0; i < N; ++i) printf("%lld\n", res[i]);
}