頭整理するのが大変だった

問題概要

$X \times Y \times Z$ 個の格子点 $(x, y, z)$ ( $x = 0, 1, \dots, X-1$ 、 $y = 0, 1, \dots, Y-1$ 、 $z = 0, 1, \dots, Z-1$ ) がある。

これらの格子点を以下のルールに則って $N$ 色 ( $0, 1, \dots, N-1$ ) で塗る。

点 $(x, y, z)$ の、 $(A, B, C)$ とのマンハッタン距離が $d$ であるとき
点 $(x, y, z)$ を、色 $d$ % $N$ で塗る

各 $i = 0, 1, \dots, N-1$ について、その色で塗られた格子点が何個あるかを出力せよ。

制約

$1 \le X, Y, Z \le 10^{6}$
$1 \le N \le 1000$

考えたこと

点 $(A, B, C)$ を頂点にもつ直方体の足し引きで実現できる。よって以下の場合に帰着して考えられる。

$x = 0, 1, \dots, a-1$
$y = 0, 1, \dots, b-1$
$z = 0, 1, \dots, c-1$

で表される $abc$ 個の格子点について、各格子点を色 $(x + y + z)$ % $N$ で塗る。各色で塗られた格子点の個数をそれぞれ求めよ。

さらに、 $a, b, c$ をあらかじめ $N$ で割ったあまりにする前処理を行う (それ以外の部分は各色が同色ずつになる)。

このとき、各 $ab$ マスについて、色 $a + b$ % $N$ を始点として連続 $c$ 色分に一様に 1 を足していく操作を行えばよい。これはいもす法で実現できる。

よって全体の計算量は $O(N^{2})$ でできる。

コード

#include <bits/stdc++.h>
using namespace std;

void add(vector<long long> &res, long long a, long long b, long long c, int N, long long add) {
    long long offset = (a * b * c - (a%N) * (b%N) * (c%N)) / N;
    a %= N, b %= N, c %= N;
    vector<long long> diff(N+1, 0);
    for (int i = 0; i < a; ++i) {
        for (int j = 0; j < b; ++j) {
            int start = (i + j) % N, goal = (start + c) % N;
            if (start <= goal) diff[start]++, diff[goal]--;
            else diff[start]++, diff[N]--, diff[0]++, diff[goal]--;
        }
    }
    for (int i = 0; i < N; ++i) diff[i+1] += diff[i];
    for (int i = 0; i < N; ++i) res[i] += (diff[i] + offset) * add;
}

int main() {
    vector<long long> v(3), p(3);
    for (int i = 0; i < 3; ++i) cin >> v[i];
    for (int i = 0; i < 3; ++i) cin >> p[i];
    int N; cin >> N;

    vector<long long> res(N, 0), a(3);
    for (int bit = 0; bit < (1<<3); ++bit) {
        for (int i = 0; i < 3; ++i) {
            if (bit & (1<<i)) a[i] = p[i]+1;
            else a[i] = v[i]-p[i];
        }
        add(res, a[0], a[1], a[2], N, 1);
    }
    for (int i = 0; i < 3; ++i) {
        a[i] = 1;
        for (int bit = 0; bit < (1<<2); ++bit) {
            for (int j = 0; j < 2; ++j) {
                if (bit & (1<<j)) a[(i+j+1)%3] = p[(i+j+1)%3]+1;
                else a[(i+j+1)%3] = v[(i+j+1)%3] - p[(i+j+1)%3];
            }
            add(res, a[0], a[1], a[2], N, -1);
        }
    }
    for (int i = 0; i < 3; ++i) {
        add(res, 1, 1, p[i]+1, N, 1);
        add(res, 1, 1, v[i]-p[i], N, 1);
    }
    add(res, 1, 1, 1, N, -1);

    for (int i = 0; i < N; ++i) {
        if (i) cout << " ";
        cout << res[i];
    }
    cout << endl;
}

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

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

AOJ 2678 Cube Coloring (JAG 春コン 2014 B) (450 点)

問題概要

制約

考えたこと

コード