AtCoder Beginner Contest 330 - 민트를 가다

C 억까..

A - 구현하면 됩니다

 

B - 뇌빼고 $A_i \in [l, r]$ 인지, 왼쪽인지 오른쪽인지 케웍을 하면 됩니다

 

C - $x \leq \sqrt{D}$ 까지 확인하며 $y$를 적당히 봐주면 되는데.. non-negative integers 가 0을 포함 하지 않는다는 능지이슈가...

 

D - 점 하나를 고정하고 구간합 등으로 개수를 세주면 됩니다. 

 

E - https://cp-algorithms.com/sequences/mex.html

라이브러리 체커 문제였습니다. 간단히 요약하자면 트리셋이나 pq같은거에 현재 수열에 없는 값들을 저장해주면 mex값은 그 중 최소가 됩니다.

 

F - 어떤 정사각형이 최소의 변 길이로 점들을 포함한다는 것은, $\max ( \max X - \min X, \max Y - \min Y)$ 이 변의 길이와 같다는 뜻입니다. 즉, $X$ 좌푯값의 최대 최소와 $Y$ 좌푯값의 최대 최소만 중요합니다. 각 $x$, $y$를 별개로 생각해줄 수 있습니다. 정사각형의 변의 길이는 이분탐색 등으로 찾아줄 수 있으니, 변의 길이에 대한 결정문제를 풀면 됩니다. 이는 각 점을 시작점으로 하는 스위핑과 끝점으로 하는 스위핑을 해주며 그 점을 기준으로 생기는 정사각형을 고려해서 구간합 등으로 움직이는 거리를 계산해주면 됩니다. 이를 구현하면 최소 연산 횟수를 알 수 있으니, 그 횟수가 K보다 작은지 확인해주면 됩니다.

 

후기 - D 웰논 E 웰논 F 웰논

너무 좋아요 웰논만 나오니.. 출제권한 B를 얻을 수 있을거라 기대해봐도 좋지 않을까.. 싶네요

다음부터는 속도를 좀 올리고 실수를 줄이는 방향으로 가야할 것 같네요 그리고 웰논 아닌 문제도 좀 푸는 연습을..