https://www.acmicpc.net/problem/22997
요약
- 좌표 평면이 주어지고(500 * 500)
- 다음 명령을 순서대로 수행했을때 처치한 적의 수를 카운트
- 특정 범위 전체를 공격하는 명령
- 특정 좌표에 적이 나타나는 명령
- 나타난 적을 퇴각 시키는 명령
- 공식 풀이 : https://github.com/justiceHui/Sunrin-Contest/blob/main/Sunrin-OI-2021/editorial.pdf
접근법
- 다차원 세그먼트 트리
- 사실 이렇게 사용하는 것이 맞는지 모르겠으나, 생각하는데로 구현해봄
- 2차원 세그먼트 트리에서 s ~ e 구간을 s ~ m, m + 1 ~ e로 나누는 아이디어를 확장해봄
- x ~ x', y ~ y' 구간을 분할한다고 하면 공간을 4개로 분할해서 가지를 4개로 만드는 아이디어
- 배열 인덱스 정리가 필요한데... 0 / 1 2 3 4 / 4 5 6 7 8 9 10 11 ... 이런식으로 나누어봄
- 대각선 처리
- 공격범위가 맨하탄 거리라서 마름모꼴로 나오고 정사각형이 아니라 대각선 처리를 해야함
- 좌표별로 x + y, x - y를 찍어보면 규칙성이 보임
- 범위의 대역을 x + y의 대역과 x - y의 대역으로 관리해서 접근해봄
- 공격의 처리
- 고민이 많았던 부분임
- 범위 공격을 할 때, 좌표 공간에 시간으로 마킹을 한다는 개념으로 가져감(시간 = 입력 순서)
- 적이 제거되는 순간의 시간과 공간에 마킹된 시간을 비교해서 적이 제거되었는지 아닌지를 판단함
- 범위에 값을 갱신하기 + 특정 좌표의 값을 알아내는 방법
- 1차원이면... +1, -1 기법으로 하면 편한데, 2차원이라 고민
- 적이 제거되는 순간의 시간을 판단하기 위해 lazy propagation은 아니지만 비슷한 처리를 함
- 범위 업데이트를 수행 - 트리의 가장 아래까지 내려가지는 않고, 중간에 범위에 걸치면 값을 갱신하고 더 안내려감
- 세그먼트 트리의 상위부터 하위의 특정점으로 내려오면서 거쳐온 값중 가장 큰 값이 해당 위치가 공격받은 마지막 시간이라는 아이디어
- 적이 퇴각할때는 입장시간 ~ 퇴각 시간 사이에 공격을 안받았으면 적은 살아있다는 체크를 함
- 공격을 받았더라도 별도로 처리를 하지는 않음. 왜냐하면 나중에 일괄로 처리할때 자동으로 처리가 될 것이므로.
- 모든 명령 처리를 끝내고 적의 정보를 파악하면서 적이 입장한 시간과 공격받은 시간을 비교해서 적을 공격한 카운팅을 함
후기
- 다른 사람들 코드보다 수행 시간이 상당히 많이 나왔지만 제한시간이 7초라 도전해봄
- 다차원 세그먼트 트리를 과연 이렇게 하는 것이 맞는지는 모르지만, 그냥 한번 zero base에서 생각해봄
- 2차원을 4개의 공간으로 나눠야해서 2차원공간을 2의 지수승 공간으로 처리해서 접근함 - 안그러면 나누고 나누고 했을때 끝부분에서 모양이 틀어짐
- 공식 해설과의 접근법이 많이 다름
newbieski