SASA Programming Contest 2023 Open Contest Div. 1

SASA Programming Contest 2023 Open Contest Div. 1에 참가했다. 아레나에 참가하고 싶었는데, 시간이 늦어서 등록을 못 했다.

 

---

A - 방형구 탐색

00:36 AC

 

쿼리를 naive하게 $O(N)$으로 구현하면 총 시간복잡도 $O(NQ)$로 통과한다.

 

 

B - 미역은 식물 아닌데요

00:40 AC

 

어떤 식물 $i$에 대해,

$P == 1$이면서 $M == 0$인 것은 항상 식물이다.

$P == 0$이거나 $M == 1$인 것은 항상 식물이 아니다.

그 외의 것들은 식물이 될 수도 있고, 되지 않을 수도 있다.

 

 

C - 가위 가위 가위

00:47 WA   00:48 AC

 

$1 \le i \le 100$에 대해, $i$번째에만 주먹을 내고 나머지는 모두 가위를 내서 대결을 총 100번 해보자.

반환 결과에 따라 머신의 $i$번째 패를 알 수 있다.

결과를 출력할 때 "!"를 출력하지 않아서 한 번 틀렸다.

 

 

D - 고인물이싫어

01:02 AC

 

모든 하수구를 시작점으로 두고 bfs로 물이 빠지는 칸을 모두 체크해두고, 직사각형 개수는 2차원 누적 합으로 구해주면 된다.

 

 

H - 방형구 탐색 (Hard)

02:30 AC

 

꽃의 종류가 10억 개라서, 좌표 압축을 써도 되지만 귀찮아서 map을 썼다.

구조는 map<int, pbds>이고, 각 pbds에는 해당 꽃이 나온 인덱스 번호를 저장한다.

꽃을 없애는 쿼리는 한 곳 당 최대 한 번만 진행하면 된다.

세그와 분할 정복의 사이 그 어딘가에 해당하는 테크닉으로 말단 정점에 가면 해당 인덱스를 pbds에서 erase해주었다.

꽃을 찾는 쿼리는 pbds의 order_of_key로 $(c+1)$미만의 개수 $- b$미만의 개수로 처리했다.

 

---