티스토리 뷰

문제 풀이

[CF 371 D] Animals and Puzzle

RiKang 2017. 10. 31. 17:37

1. DP[i][j] = (i, j)가 오른쪽 밑 모서리인 정사각형의 최대 크기


1-(1). (i,j) 가 0인 경우 -> DP[i][j]=0;


1-(2). (i,j) 가 1인 경우 -> min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1


2. parametric search


3. 쿼리의 정답이 특정 값 mid 이상인지 여부는 DP 배열을 소스로 만든 sparse table을 통해 바로 알 수 있음.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef short node_type;
 
namespace MIN_ver{
    node_type INIT = 1000000000;
    node_type node_calc(node_type n1, node_type n2){return min(n1,n2);}
}
 
namespace MAX_ver{
    node_type INIT = 0;
    node_type node_calc(node_type n1, node_type n2){return max(n1,n2);}
}
 
using namespace MAX_ver;
 
const int N = 1005, log_N = 11, M = 1005, log_M = 11;
 
struct sparse_table{ // 0-based
    int n1,m1;
    node_type T[N][M][log_N][log_M];
    node_type res[N][M]; // res : 기존 배열
    int cal_d[N+M];
    void init(int n2,int m2){
        n1=n2,m1=m2;
        for(int i=1; i<N+M; i++){
            cal_d[i] = cal_d[i-1];
            while((1<<cal_d[i])<=i) cal_d[i]++;
            cal_d[i]--;
        }
        for(int i=0; i<n1; i++)
            for(int j=0; j<m1; j++)
                T[i][j][0][0= res[i][j];
        for(int di=0; di<log_N; di++){
            if(di==0){
                for(int dj=1; dj<log_M; dj++)
                    for(int i=0; i<n1; i++)
                        for(int j=0; j+(1<<dj)<=m1; j++)
                            T[i][j][di][dj] = node_calc(T[i][j][di][dj-1], T[i][j+(1<<(dj-1))][di][dj-1]);
            }
            else{
                for(int dj=0; dj<log_M; dj++)
                    for(int i=0; i+(1<<di)<=n1; i++)
                        for(int j=0; j+(1<<dj)<=m1; j++)
                            T[i][j][di][dj] = node_calc(T[i][j][di-1][dj], T[i+(1<<di-1)][j][di-1][dj]);
            }
        }
    }
    node_type query(int x1, int y1,int x2, int y2){
        if(x1>x2 || y1>y2) return INIT;
        int d1 = cal_d[x2-x1+1];
        int d2 = cal_d[y2-y1+1];
        int x3 = x2-(1<<d1)+1;
        int y3 = y2-(1<<d2)+1;
        node_type ret = T[x1][y1][d1][d2];
        ret = node_calc(ret, T[x1][y3][d1][d2]);
        ret = node_calc(ret, T[x3][y1][d1][d2]);
        ret = node_calc(ret, T[x3][y3][d1][d2]);
        return ret;
    }
}table;
 
int n,m;
int a[N][N];
int sum[N][N];
 
bool chk(int x1,int y1,int x2,int y2){
    return (x2-x1+1)*(y2-y1+1== sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
 
int main(){
    scanf("%d %d",&n,&m);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&a[i][j]);
            sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            table.res[i][j] = 0;
            for(int k=i-table.res[i-1][j-1]; k<=i; k++){
                if(chk(k,j-(i-k),i,j)){
                    table.res[i][j] = i-k+1;
                    break;
                }
            }
        }
    }
    table.init(n+1,m+1);
    int t;
    scanf("%d",&t);
    while(t--){
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int l = 0;
        int r = min(x2-x1+1, y2-y1+1)+1;
        while(l+1<r){
            int mid = (l+r)/2;
            if(table.query(x1+mid-1,y1+mid-1,x2,y2)<mid) r = mid;
            else l = mid;
        }
        printf("%d\n",l);
    }
    return 0;
}
cs


'문제 풀이' 카테고리의 다른 글

[BOJ 13548] 수열과 쿼리 6  (0) 2017.11.11
[BOJ 13518] 트리와 쿼리 9  (0) 2017.11.03
[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31