Wonseok Shin | 8월 2주차 Weekly PS

Back to : ps-weekly

Contents

August 09 - August 15, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 올려놓은 코드를 볼 수 있습니다.

읽는 사람이 문제를 읽고 조금 생각해봤다고 가정하고, 대략적인 아이디어만 간단히 적을 생각입니다 ㅎㅎ

Recent Updates

Div.2 136등, Rating 2055->2117
Performance 2271
E번에서 mod 10억 7인줄 알고 (998,244,353입니다) 문제를 제대로 안읽어서 25분의 디버깅 시간과 1틀을 헌납했습니다. 그게 아니었다면 아마 100등 정도 했을텐데 아쉽네요.
그외에는 라운드 자체는 굉장히 재밌었습니다. 라운드 전체에 대한 풀이글은 D2를 업솔빙한 후에 작성할 예정입니다.

기하 연습셋을 만들어서 돌았습니다.

난이도 Gold II
기하를 열심히 하면 풀 수 있습니다.
가운데 원은 넓이와 둘레의 관계를 통해 구할 수 있고, 나머지는 침착하게 삼각비를 이용하여 모든 값을 계산하면 됩니다.
매번, 세 방향으로 원을 그릴 수 있습니다. 세 방향 중 가장 큰 원 쪽에 원을 그리고, 그쪽 방향의 원 크기를 줄이는 식으로 구현하면 됩니다.
종이에 삼각비를 열심히 계산하면 문제 자체는 어렵지 않습니다.

난이도 Platinum V
$n$개의 점에서, 가장 큰 정사각형의 넓이를 구하는 문제.
가장 쉬운 방법은 점 $p$ 를 고정하고, 다른 점 $x, y$ 로 변을 그어서 (직각인 경우), $p, x, y$ 와 함께 정사각형을 이루는 $q$가 존재하는지 확인해볼 수 있겠습니다. 이는 각 $p$에 대해 $n^2$ 번의 확인이 필요하므로 $O(n^3)$ 알고리즘입니다.
이 방법으로는 해결이 불가능합니다. 좀더 복잡도를 줄이기 위해, 대각선을 고정하겠습니다.
대각선을 하나 고정하면, 다른 대각선을 그어서 나머지 두 점의 위치를 특정할 수 있습니다. 나머지 두 점이 $n$개의 점중에 있는지 확인하면 되고, 이는 set같은걸 쓰면 $O(n^2 \log n)$ 에 할 수 있습니다.
제한 시간이 무려 10초임에도 불구하고 시간이 상당히 빡빡합니다. 저는 set에 point를 넣는 것이 느린건가 싶어서 점의 $x, y$ 좌표를 잘 때려넣어서 long long int 하나로 바꿨더니 간당간당하게 통과했습니다.
팁으로, 대각선에 대해 다른 두 점의 위치를 구하는 방법중 하나는 벡터연산을 잘 하면 되는데 그 과정에서 벡터에 1/2배를 해야 합니다. 이런 문제를 해결할 때는 모든 좌표를 2배로 늘려서 구현하면 조금 쉬워집니다.

난이도 Platinum I
바로 위 위 문제인 9015와 거의 비슷한데, 직사각형 버전입니다.
다양한 방법으로 복잡도를 줄일 수 있습니다. 저는 모든 $n^2$ 개의 쌍에 대해 두 점 사이에서 오른쪽 방향으로 가는 벡터를 저장하되 ($x$좌표가 같으면 위 방향)
map을 이용하여 <오른쪽으로 가는 벡터 : {시작점들의 리스트}> 를 저장했습니다. 이제, 어떤 오른쪽 방향의 벡터 $p$에 대해, 두 시작점 $x, y$ 가 있다면, $x$ 와 $x+p$, $y$, $y+p$ 가 모두 $n$개의 점들 중에 있었다는 말이므로, 벡터 $r = y - x$ 를 계산하여 $r$과 $p$가 수직한지 관찰하면 됩니다.
복잡도는 $n^2 \log n$ 인데, 여전히 key와 value가 point와 point list 인 맵이 너무 느립니다. 9015번처럼, 점을 잘 숫자로 인코딩하면 간당간당하게 통과 가능했습니다. 범위를 잘 보고 이렇게 하면 됩니다.
```
const int B = (int) 1e9;
const int M = (int) 1e8;
inline int ptoi (P p) {
  return (p.x + M)*B+(p.y+M);
}
inline P itop(int x) {
  return P((x/B - M),((x%B)-M));
}
```