AOJ 3045 Painting (ACPC 2018 day2 G)

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

問題へのリンク

問題概要

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

• 各 に対し、 を で割った余りを に加える。

制約

• 
• <

考えたこと

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

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

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

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

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

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

最終的な計算量は

#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]);
}