【PGBATTLE2019_かつおぶし3】聴取
[Q] https://products.sint.co.jp/q_list
マンハッタン距離をそのまま扱うと、
4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
となって、二次元座標としては扱いにくい。
座標を45度回転させることで、縮尺はルート2倍されるが
2 2 2
1 1
2 0 2
1 1
2 2 2
マンハッタン距離なので埋めてよくて
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2
管理を変えられる。
Q. 座標の回転?
A. (x, y) = (x-y, x+y)
にするのが一般的かも。この回転で、原点を中心に-45度回る。縮尺はルート2倍に大きくなるけど、マンハッタン距離で計算する世界なので、x+yは変わらない。
1,1の点が0,2に動く。
これに従って、
x+y は 0~6000,
x-y は -3000 ~ 3000
まで取りうるので、x-yには+3005 の補正をするといい。
DP[6010][6010] = 要素の有無 でデータ管理。
二次元累積和をして、
DP[6010][6010] = 自分含め左上の要素の総数 で管理される
Q. 二次元累積和?
A. 4点の足し引きで、範囲の要素数を導けます。
0 0 0 0 0 0
0<0>0 1<1>1
0 0 0 1 1 1
0 0 0 2 2 2
0<0>0 2<3>3
0 0 0 2 3 3
DP[4][4] - DP[1][4] - DP[4][1] + DP[1][1]
3 - 1 - 0 + 1
をすることで、
(2,2) ~ (4,4)の要素数の総和が得られる。
実装。
ll DP[6010][6010];
ll X[300010];
ll Y[300010];
ll D[300010];
ll A[300010];
ll B[300010];
int main(){
cincout();
// かいてん
// x-y, x+yにする
// x = -3000 ~ 3000
// y = 0 ~ 6000
// x座標は+3000の補正
ll N;
cin >> N;
rep(i, N) cin >> X[i] >> Y[i] >> D[i];
rep(i, N){
A[i] = X[i] - Y[i] + 3000;
B[i] = X[i] + Y[i];
++DP[B[i]][A[i]]; // いもす
}
rep(i, 6001){
ll t=0;
rep(j, 6001){
t += DP[i][j];
DP[i][j] = t;
}
}
rep(j, 6001){
ll t=0;
rep(i, 6001){
t += DP[i][j];
DP[i][j] = t;
}
}
rep(i, N){
ll ans = 0;
ll a=A[i], b=B[i], d=D[i];
ans += DP[min(6000, b+d)][min(6000, a+d)];
if (b-d>0) ans -= DP[b-d-1][min(6000, a+d)];
if (a-d>0) ans -= DP[min(6000, b+d)][a-d-1];
if (b-d>0 && a-d>0) ans += DP[b-d-1][a-d-1];
cout << ans << endl;
}
}
この記事が気に入ったらサポートをしてみませんか?