Bomber Game

問題を解くためには、爆弾による効果の範囲に対する区間の加算を高速で行う必要があります。

今回のような問題においては、二次元いもす法というアルゴリズムが有効です。

便宜上、爆弾が高度を減少させるものと考えるとややこしいため、高度を増加させるものとして考えます。

威力 $1$ の爆弾の場合を例に示すと、図１のような加算を行った後に、左下方向に累積和をとり (図２)、右下方向に累積和をとると (図３)、爆弾の範囲に $1$ だけ加算されていることが分かります。

 0  0  1  0  0
 0  0  1  0  0
-1 -1  0 -1 -1
 0  0  1  0  0
 0  0  1  0  0

 0  0  1  0  0
 0  1  1  0  0
 0  0  0 -1 -1
 0  0  0 -1  0
 0  0  0  0  0

 0  0  1  0  0
 0  1  1  1  0
 0  0  1  0  0
 0  0  0  0  0
 0  0  0  0  0

今回の問題では、最終的な高度を求めたいので、図１のような加算をそれぞれの爆弾について行い、その後に累積和を求めることによって高速に高度を求めることができます。

よって、この問題を $O(N^2 + M)$ で解くことができました。

実装においては、配列の範囲外参照に十分に注意してください。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> p(m), r(m), c(m);
    for(int i = 0; i < m; i++){
        cin >> p[i] >> r[i] >> c[i];
        r[i]--; c[i]--;
        r[i] += 2 * n; c[i] += 2 * n;
        if(p[i] > 2 * (n - 1)) p[i] = 2 * (n - 1);
    }
    vector<vector<int>> imos(5 * n + 1, vector<int>(5 * n + 1));
    for(int i = 0; i < m; i++){
        imos[r[i] - p[i]][c[i]] += 1;
        imos[r[i] - p[i] + 1][c[i]] += 1;
        imos[r[i] + 1][c[i] - p[i] - 1] += -1;
        imos[r[i] + 1][c[i] - p[i]] += -1;

        imos[r[i] + 1][c[i] + p[i]] += -1;
        imos[r[i] + 1][c[i] + p[i] + 1] += -1;
        imos[r[i] + p[i] + 1][c[i]] += 1;
        imos[r[i] + p[i] + 2][c[i]] += 1;
    }

    vector<pair<int, int>> down_left, down_right;
    for(int i = 0; i < 5 * n; i++){
        down_left.push_back({0, i});
        down_right.push_back({0, i});
    }
    for(int i = 1; i < 5 * n; i++){
        down_left.push_back({i, 5 * n - 1});
        down_right.push_back({i, 0});
    }
  
    // 左下方向
    for(auto p : down_left){
        int x = p.first, y = p.second;
        while(x + 1 < 5 * n && 0 <= y - 1){
            imos[x + 1][y - 1] += imos[x][y];
            x++; y--;
        }
    }

    // 右下方向
    for(auto p : down_right){
        int x = p.first, y = p.second;
        while(x + 1 < 5 * n && y + 1 < 5 * n){
            imos[x + 1][y + 1] += imos[x][y];
            x++; y++;
        }
    }
  
    vector<int> ans(m + 1);
    for(int i = 2 * n; i < 3 * n; i++){
        for(int j = 2 * n; j < 3 * n; j++){
            ans[abs(imos[i][j])]++;
        }
    }
    for(int i = 0; i < m + 1; i++){
        if(i >= 1) cout << " ";
        cout << ans[i];
    }
    cout << endl;
}