NYPC 2018 후기

10/27에 NYPC 2018 본선을 쳤다. 약을 대충 먹었더니 시험 이틀 전부터 감기가 심해졌는데, 다행히 당일에는 그나마 나았다. 그 때문에 머리가 이상하게 굴러가서 시험 중에 온갖 말같지도 않은 실수를 꽤 했다. 디버깅용 printf 안 지우고 삽질한것도 10번쯤 되는 것 같다.

시험 시작 전에는 그냥 기하가 안 나오기를 기도했다. (yclock이 플로우와 SA중 하나는 나온다에 코포 계정을 걸었다. 언제 터트리나요?) 자고 싶은데 카메라가 많아서 자기엔 부담스러웠다.

문제 6. $A_i+A_j+A_k=w$인 $(i, j, k)$ 순서쌍의 경우의 수 구하기, $N\leq 5000$, $w\leq 3\times 10^9$ $(i < j < k)$

1214 문제가 12345번이라서 1519 문제는 6부터 시작하는듯 하다.

보자마자 https://www.acmicpc.net/problem/2473 이 문제가 생각났는데 사실 많이 다르다.

$A_i$를 long long으로 선언하기는 싫고 $w$는 int를 넘어서 짜증났다. 결국 $A_i$는 int로 했던것 같다.

$N$이 $5000$인데 $O(N^2logN)$이 될지는 모르겠지만 첫 문제니까 대충 하면 되겠지 싶어서 그냥 map에다가 $N^2$개를 박았는데 wall clock이 떴다. 메모리 제한을 봤더니 64MB더라. 첫 문제인데 통 크게 1024MB 주면 안되나 ㅂㄷ

그래서 map에 $N$개만 넣었더니 TLE가 났다. 결국 울면서 sort lower_bound upper_bound로 풀었다. 시간은 꽤 많이 지난 것 같다.

문제 7. 길이 $L$ 막대가 벽에서 미끄러지는데, 주어진 점이 막대와 만나는지 판별하기

분명 수학문제로 본 적이 있는 것 같은데 기억이 안났다. 나중에 들어보니 $x^{2/3}+y^{2/3}\leq L^{2/3}$이라고 한다.

$(a, 0)$과 $(0, \sqrt{1-a^2})$를 연결하는 직선에서 $a$로 삼분탐색해서 풀었다. 멍청하게 y좌표 제곱으로 비교해놓고 음수 처리 안해서 계속 틀렸다.

문제 8. 직사각형을 잡아서 색칠할 수 있는데, 주어진 모양을 만들기 위해 색칠하는 횟수를 충분히 적게 해야 한다.

처음에는 outputonly길래 그냥 넘겼다. 9번 풀고 10번에서 토하고 난 뒤 돌아와서 풀었다.

점수 식이 선형이라서 0.x점 차이가 나기 쉬운 문제였다. 점수 식을 너무 대충 한듯.

(1) 1, 2번 데이터

$1\times 30$ 격자판이다. $N$을 가로 길이라고 해놓고 실제로는 행 개수라서 화났다.

처음에 전체를 한 색으로 칠한 후 손으로 잘 하면 풀린다.

(2) 3, 4번 데이터

$5\times 5$ 격자판이다. 이거도 손으로 풀었다.

(3) 5, 6번 데이터

이 데이터는 $30\times 30$ 격자판에서 전체를 한 색으로 칠한 뒤, 랜덤 직사각형을 몇번 칠해서 만들었다고 한다.

이거도 손으로 풀었는데, 30쯤 되니까 눈이 아팠다.

(4) 7, 8번 데이터

$30\times 30$ 격자판에 랜덤으로 색칠되어 있고, 색칠 횟수가 $\frac{NM(C-1)}{C}$회 이하여야 한다.

가장 많은 색으로 전체를 칠하고 $1\times 1$ 격자를 일일히 칠해주면 된다.

(5) 9, 10번 데이터

7, 8번과 같은 상황에서 색칠 횟수가 $\frac{NM(C-1)}{2C}$회 이하여야 한다.

일단 처음에 한 색을 정해서 전체를 칠했다. 그 후 원하는 색이 안 칠해진 격자는 색 -1로 칠했다고 하자. 임의의 격자를 잡고 이 격자에 색 C를 칠하고 싶다고 하자. 좌우로 -1이나 C가 칠해진 격자들만 이용해서 최대한 뻗어나간 길이와 상하로 뻗어나간 길이 중 긴 것을 골라서 그 방향으로 전부 칠한다. 임의의 격자를 선택하는 순서를 대충 하면 9번 데이터에서 10점, 10번 데이터에서 9.95점이 나온다. 이제 임의의 격자를 고르는 방법을 중앙에서 시작해서 대충 지그재그로 하면 10번 데이터에서 298번 색칠하게 되어 10점이 나온다.

문제 9. $1000\times 1000$ 격자판에 연결된 벽들이 있다. 두 격자 사이의 거리 쿼리를 $Q\leq 200000$개 처리해야 한다.

이거도 어디서 본 문제 같은데 격자 문제라서 보자마자 스트레스가 쌓였다. IOI ideal city와 같은 상황으로, 모든 열린 격자들을 좌우 격자와 합쳐주면 트리 모양이 되어 LCA로 답을 구할 수 있다.

sparse table을 만들고 싶은데 메모리가 빡세보여서 pair<short, short> 같은거를 썼다. x y 좌표 헷갈려서 몇번 틀렸다.

문제 10. 좌표평면의 두 점 사이를 이동하기 위해 지나야 하는 최소 선분 개수

문제를 열자마자 이상한 그림이 있어서 1차로 스트레스가 쌓였다. 문제를 읽어보니 https://www.acmicpc.net/problem/15308 이 문제가 생각나서 2차로 스트레스가 쌓였다. 저 문제를 처음 봤을때 토가 나와서 던졌는데, 좀 더 구데기같은 문제가 나올 줄은 몰랐다.

1번 섭태는 다각형 여러개, 2번 섭태는 컴포넌트 하나였는데, 2번 섭태는 왜 있는지 잘 모르겠다. 1번 섭태나 긁어야지 하고 이상한 BFS를 짰다가 틀린 후 8번으로 돌아갔다.

다시 돌아온 뒤에는 1번 섭태가 그냥 다각형 내부 판별만 하면 끝나는 걸 깨달았다. $(x, y)$와 $(10^9+1, y+1)$를 잇는 선분과 다각형이 홀수번 교차하면 내부, 짝수번 교차하면 외부이다. 선분 교차는 ccw 4번으로 쓱싹할 수 있다. 반직선을 약간 기울어지게 잡으면 평행이거나 끝점에서 만나는 경우의 예외가 사라져서 ㄱㅇㄷ인데 rkm은 예외 처리를 다 해준듯 하다.

2번 섭태 이상은 풀이는 뻔하지만 별로 하고싶지 않았다. 선발고사 때는 뭔가 인생이 걸린 문제라고 생각해서 더 구데기같은거도 열심히 짰지만, 이 문제 안푼다고 인생이 바뀔 것 같지도 않고, 결정적으로 427이면 본상을 받기 충분하다고 생각했다.

427을 받은 후 1시간 쯤 남았던 것 같은데, 시작하기 전과 마찬가지로 자고 싶었는데 카메라때문에 못 자고 8번 풀이 개선을 도전했으나 실패했다.

결국 은상을 받았다. 문제들이 전체적으로 생각보다는 지식이 필요한 문제들에 가까웠던 것 같다. 여담으로 IOI contestant들이 123등을 싹쓸이했다. IOI 성적 역순