[ABC228] F - Stamp Game
[Q] https://atcoder.jp/contests/abc228/tasks/abc228_f
1. 白の長方形の大きさ (h2, m2) は、黒より大きくても意味をなさないので、h2 = min(h1, h2)
w2 = min(w1, w2) をとっておく。
2. 二次元累積和で、白と黒の面積を求めておく。
3. 黒の面積を全探索。つど白の最大妨害値を探す。
4. しかし愚直な白探しにO(黒の面積) かかっちゃう。
4. 白探しの高速化のために、まずx座標をkey、白面積をvalにしたセグ配列をつくる。そこでえたクエリについて、y座標をkey、クエリをvalにしたセグ配列を作る。二次元セグ木？ 下準備を経て、白の最大妨害値が、O(log(h1-h2) + log(w1-w2)) ですぐ求まる。
Q. 入力例1
3 4 2 3 3 1
3 1 4 1
5 9 2 6
5 3 5 8
1. 白面積を黒面積にあわせる。
黒面積: 2*3
白面積: 3*1
------
min 2*1 = h2, w2
黒2*3 から
###
###
白3*1を除くと、2*1しかかぶらない
.## #.# ##.
.## #.# ##.
2. 二次元累積和で、黒面積 と 白面積 を求めておく。
長方形の「右下の角位置」を基準にする。左上への範囲をとると想定。
--- 累積和 acc ---
3 4 8 9
8 18 24 31
13 26 37 52
--- 黒面積 B ---
0 0 0 0 // 3 1 4 x
0 0 24 23 // 5 9 2 x = 24
0 0 29 33 // x x x x
--- 白面積 T ---
0 0 0 0
8 10 6 7
10 12 7 14
3. 黒の面積を全探索し、つど白の最大値をもとめる。
1. 黒(1,2) = 24のとき、
###.
###.
....
考慮すべき白位置は3つ。
1) 白(1,0) 24-8
-##.
-##.
....
1) 白(1,1) 24-10
#-#.
#-#.
....
1) 白(1,2) 24-7
##-.
##-.
....
白のmaxをとるので、この黒の候補値は 24-10 = 14。
4. こんな感じに、愚直な白探索だと間に合わない。セグ木で下準備をしておく。
---白面積の行セグZ --- これは 白面積Tとまったく同じ値を入れる。
Z[0] = 0 0 0 0
Z[1] = 8 10 6 7
Z[2] = 10 12 7 14
|-----|
白面積の探索すべき列は、w1-w2+1 = 3-1+1 = 3
このセグZをもとに、列セグEをとる。
--- 白面積の列セグE ---
E[0] E[1] E[2] E[3]
-1 -1 0 0
-1 -1 10 10 | 白の探索すべき行は、h1-h2+1 = 0-0+1 = 1
-1 -1 12 14
必要な値はそろった。
E[列].query(行)
黒(1,2) - E[2].query(1,2) = 24 - 10 = 14 // 白の(1,2)をとりたい
黒(1,3) - E[3].query(1,2) = 23 - 10 = 13
黒(2,2) - E[2].query(2,3) = 29 - 12 = 17
黒(2,3) - E[3].query(2,3) = 33 - 14 = 19
--- 黒面積 B ---
0 0 0 0
0 0 24 23
0 0 29 33
最大値をとる 19 が解答。Q. 白セグ木のquery範囲を考える
Q. 入力例3
10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19
---累積和 A---
9 16 35 42 52 56 69 78 82 90
19 41 76 86 114 137 167 188 205 215
31 71 110 129 170 206 242 276 298 310
47 99 140 173 232 285 335 376 406 430
59 124 182 227 300 368 437 485 528 567
64 131 205 260 337 411 481 531 581 628
74 155 243 308 394 481 562 616 675 741
90 183 274 358 463 556 639 712 785 871
105 201 311 414 521 624 708 785 861 962
118 234 349 458 584 688 779 873 959 1079
---黒面積 B---
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 242 245 227 200
0 0 0 0 0 0 266 260 241 235
0 0 0 0 0 0 270 257 240 246
0 0 0 0 0 0 239 222 223 223
0 0 0 0 0 0 227 213 213 208
0 0 0 0 0 0 202 196 198 212
0 0 0 0 0 0 227 213 210 228
0 0 0 0 0 0 217 213 205 232
---白面積 T---
0 0 0 0 0 0 0 0 0 0
0 0 76 67 73 61 81 74 68 48
0 0 75 65 63 75 86 80 66 47
0 0 64 59 60 84 81 70 53 47
0 0 72 70 77 90 97 79 68 62
0 0 65 70 73 61 59 50 49 52
0 0 61 66 63 52 44 37 34 49
0 0 69 72 74 76 60 55 59 85
0 0 68 75 81 75 40 42 43 75
0 0 75 72 70 57 40 40 42 68
Q. queryの範囲は？
黒:3*7
白:2*3
なので、
A. Zセグの探索列は、w1-w2+1 = 7-3+1 = 5列
黒 3*7 について
#######
#######
#######
白 2*3 を、列移動でどれだけとれるか
...#### ####...
...#### -> ####...
####### #######
右下位置だけでみると
0123456 0123456
....... .......
..x.... -> ......x 2 <= x <= 6 の範囲をとる。 w1-w2+1 = 7-3+1 = 5列を探索するとわかる。
....... .......
---白の行セグ Z---
0 0 0 0 0 0 0 0 0 0
0 0 76 67 73 61 81 74 68 48
0 0 75 65 63 75 86 80 66 47
0 0 64 59 60 84 81 70 53 47
0 0 72 70 77 90 97 79 68 62
0 0 65 70 73 61 59 50 49 52
0 0 61 66 63 52 44 37 34 49
0 0 69 72 74 76 60 55 59 85
0 0 68 75 81 75 40 42 43 75
0 0 75 72 70 57 40 40 42 68
|------------| 5列を探索して、Eセグをとる。
---白の列セグ E--- ---黒面積 B--
E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 0 1 2 3 4 5 6 7 8 9
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 81 81 81 81 1 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 86 86 86 86 2 0 0 0 0 0 0 242 245 227 200
-1 -1 -1 -1 -1 -1 84 84 84 84 3 0 0 0 0 0 0 266 260 241 235
-1 -1 -1 -1 -1 -1 97 97 97 97 4 0 0 0 0 0 0 270 257 240 246
-1 -1 -1 -1 -1 -1 73 73 73 61 5 0 0 0 0 0 0 239 222 223 223
-1 -1 -1 -1 -1 -1 66 66 63 52 6 0 0 0 0 0 0 227 213 213 208
-1 -1 -1 -1 -1 -1 76 76 76 85 7 0 0 0 0 0 0 202 196 198 212
-1 -1 -1 -1 -1 -1 81 81 81 75 | 8 0 0 0 0 0 0 202 196 198 212
-1 -1 -1 -1 -1 -1 75 72 70 68 | 9 0 0 0 0 0 0 217 213 205 232
2行がqueryの対象
A. Eセグの探索行は、h1-h2+1 = 2行
E[列].query(行)
黒(2,6) - E[6].query(1,3) // queryは[a, b) でとる。白(1,6)と白(2,6)を探索したい
黒(2,7) - E[7].query(1,3)
黒(2,8) - E[8].query(1,3)
黒(2,9) - E[9].query(1,3)
黒(3,6) - E[6].query(2,4)
黒(3,7) - E[7].query(2,4)
黒(3,8) - E[8].query(2,4)
黒(3,9) - E[9].query(2,4)
...
最大値をとる 180 が解答。実装
ll A[1010][1010]; // 累積和
ll B[1010][1010]; // 黒面積
ll T[1010][1010]; // 白面積
ll H, W, h1, w1, h2, w2;
RangeMax Z[1010]; // 白 Z[y][x]についてのセグ
RangeMax E[1010]; // 白 E[x][y]についてのセグ
int main(){
cincout();
cin >> H >> W >> h1 >> w1 >> h2 >> w2;
chmin(h2, h1);
chmin(w2, w1);
// 累積和
rep(i, H) rep(j, W) cin >> A[i][j];
rep(i, H){
rep(j, W-1) A[i][j+1] += A[i][j];
}
rep(j, W){
rep(i, H) A[i+1][j] += A[i][j];
}
// B
for(ll i=h1-1; i<H; ++i){
for(ll j=w1-1; j<W; ++j){
B[i][j] = A[i][j];
ll ni=i-h1;
ll nj=j-w1;
if (ni>=0) B[i][j] -= A[ni][j];
if (nj>=0) B[i][j] -= A[i][nj];
if (ni>=0 && nj>=0) B[i][j] += A[ni][nj];
}
}
// T
for(ll i=h2-1; i<H; ++i){
for(ll j=w2-1; j<W; ++j){
T[i][j] = A[i][j];
ll ni=i-h2;
ll nj=j-w2;
if (ni>=0) T[i][j] -= A[ni][j];
if (nj>=0) T[i][j] -= A[i][nj];
if (ni>=0 && nj>=0) T[i][j] += A[ni][nj];
}
}
// Zセグ
rep(i, H) Z[i].init(1010);
rep(i, W) E[i].init(1010);
rep(i, H){
rep(j, W){
Z[i].update(j, T[i][j]);
}
}
ll dx = w1-w2;
ll dy = h1-h2;
// Eセグ
// 黒の長方形が入る箇所すべてを調べる
rep(i, H){
for(ll j=w1-1; j<W; ++j){
ll high = Z[i].query(j-dx, j+1);
E[j].update(i, high);
}
}
ll ans = 0;
rep(i, H){
rep(j, W){
ll b = B[i][j];
if(b==0) continue;
ll high = E[j].query(i-dy, i+1);
chmax(ans, b-high);
}
}
cout << ans << endl;
}https://atcoder.jp/contests/abc228/submissions/27414486
40分しかなかった。行セグして、列セグしなくて、ちょっとTLE。残念。
はじめてのセグ配列で脳メモリがきれた。
この記事が気に入ったらサポートをしてみませんか？