NYPC 2018 본선 복기 및 후기

NYPC 2018 본선이 10월 27일 있었다. 결과는 5등으로, 동상을 받았다. 예상보다 성적이 잘 나온 것 같다 ㅋㅋ

올해 정올 본선을 걸렀고, 작년 NYPC에서는 아깝게 동상을 못 받아서 올해 NYPC에서 상을 꼭 타고 싶었는데, 기분이 좋다. 

작년에는 없었던 100만원 장학금도 받았고, 부상으로 LG 그램 노트북을 받았다. 대학교에 가면 쓰게 될 것 같다.

간략한 문제 설명과 Subtask 설명을 쓰고, 내가 시험을 친 과정을 적는다. 오류가 있다면 지적 대환영 :) 

________________________________________________________________________________________________________________________

문제

1. $1 \le N \le 5000$과  $1 \le W \le 10^9$이 주어진다. 

또한, 서로 다른 자연수 $1 \le A_1, A_2, \cdots A_n \le 10^9$이 주어진다. 

이때, $i<j<k$이고 $A_i+A_j+A_k=W$를 만족하는 순서쌍 $(i,j,k)$의 개수를 구하시오. 

제한시간 1초, 배점 100

Subtask 1. $N \le 300$ 

Subtask 2. $W \le 3 \cdot 10^6$

Subtask 3. 추가 제한 없음

2. 실수 $1 \le L \le 100$이 주어진다. $xy$ 평면 위에 길이가 $L$인 막대기가 두 개 있다. 또한, $x=0$과 $x=2L$에 벽이 있다. 

처음에 두 막대기는 벽 $x=0$, $x=2L$에 각각 붙어있다. 

즉, 한 막대기는 양 끝점이 $(0,0), (0,L)$이고, 다른 막대기는 양 끝점이 $(2L,0),(2L,L)$이다.

이제 두 막대기가 한 끝점은 벽 위에 있는 상태로 미끄러져 내려온다. 최종 상태에서는 두 막대기가 $(L,0)$에서 만난다.

이제 한 점 $(x,y)$가 주어진다. 두 막대기가 미끄러져 내려오는 과정에서, $(x,y)$가 막대기와 만나는 지 여부를 판별하시오.    

제한시간 1초, 배점 100

Subtask 없음. 

3. 파일로 주어진 input 10개에 대해, output을 뽑아 점수를 얻는 Output Only 문제이다.

자연수 $1 \le N, M \le 30, 1 \le C \le 3, V$가 주어진다. 

그 후, 각 격자가 $1, 2, \cdots C$번의 색깔 중 하나로 색칠되어 있는 $N \times M$ 직사각형이 주어진다. 

각 행은 1번부터 $N$번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 $M$번까지 번호가 붙어있다.

다음 조건을 만족하는 $T$와, $r_{1,i}, c_{1,i}, r_{2,i}, c_{2,i}, color_i$ $(1 \le i \le T)$를 출력하시오. 

단, $1 \le r_{1,i} \le r_{2,i} \le N$, $1 \le c_{1,i} \le c_{2,i} \le M$, $1 \le color_i \le C$를 만족해야 한다.

조건: 색칠이 되어있지 않은 $N \times M$ 직사각형이 있다. 

각 행은 1번부터 $N$번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 $M$번까지 번호가 붙어있다.

각 $1 \le i \le T$에 대하여, 직사각형 $[r_{1,i}, r_{2,i}] \times [c_{1,i}, c_{2,i}]$에 속한 격자의 색깔을 $color_i$로 바꾼다.

이때, 얻어진 결과물이 입력에서 주어진 $N \times M$의 직사각형과 동일하다. 

Input은 총 10개고, 각각에서 얻을 수 있는 최대 점수는 10점이다. 점수는 다음과 같이 계산된다.

1. 우선 출력된 결과물이 조건에 맞지 않으면, 0점이다.

2. $T < V$이면 10점이고, $T \ge N \cdot M$이면 1점이다.

3. 그 외의 경우, $10 - 9 \cdot \frac{T-V}{NM-V}$점을 부여한다. 

데이터 1, 2: $N=1$ 랜덤 데이터. 데이터 1은 $C=2$, 데이터 2는 $C=3$. $V$는 최적의 $T$값 + 1으로 주어짐.

데이터 3, 4: $N, M$이 작은 랜덤 데이터. 데이터 3은 $C=2$, 데이터 4는 $C=3$. $V$는 최적의 $T$값 + 1으로 주어짐.

데이터 5, 6: 직사각형 전체를 한 색으로 칠하고, 랜덤한 직사각형 $V-1$개를 골라 색칠하여 만들어진 데이터.

데이터 5는 $C=2$, 데이터 6은 $C=3$으로, 두 데이터 모두 $N, M$이 20 이상으로 크다. 

데이터 7, 8: $N=M=30$인 랜덤 데이터. 데이터 7은 $C=2$, 데이터 8은 $C=3$. $V = NM \cdot \frac{C-1}{C}$.

데이터 9, 10: $N=M=30$인 랜덤 데이터. 데이터 7은 $C=2$, 데이터 8은 $C=3$. $V = NM \cdot \frac{C-1}{2C}$.

4. 자연수 $1 \le N, M \le 1000$이 주어진다. 

$N \cdot M$ 격자로 이루어진 공간이 있는데, 이 중 일부 격자는 지나갈 수 없는 격자이다. 

단, 지나갈 수 없는 격자들은 상하좌우로 인접한 것은 연결되어 있다고 하면, 하나의 컴포넌트로 연결되어 있다.

또한, $N \cdot M$ 격자로 이루어진 공간에서 가장 바깥쪽 행/열들은 모두 지나갈 수 없는 격자이다.

각 행은 1번부터 $N$번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 $M$번까지 번호가 붙어있다.

이제 $1 \le Q \le 2 \cdot 10^5$개의 쿼리가 주어진다. 

각 쿼리는 두 점 $(sy,sx)$, $(ey,ex)$으로 이루어지며, 두 점 사이의 최단 경로의 거리를 답해야 한다. 

단, 경로가 존재하지 않는 경우에는 -1을 출력하면 된다. $Q$개의 쿼리에 모두 답하시오. 

시간제한 2초, 배점 100

Subtask 1. (19점) $N, M, Q \le 300$

Subtask 2. (21점) $N \le 4$

Subtask 3. (26점) $M=2k+1$로 홀수이다. 주어지는 공간은 다음 조건들을 만족한다.

조건 1. $(2,k+1), (3,k+1), \cdots (N-1,k+1)$은 모두 지나갈 수 있는 격자들이다. 

조건 2. $(u,v)$가 지나갈 수 있는 격자이면, 임의의 자연수 $v' \in [v,k+1]$에 대하여 $(u,v')$도 지나갈 수 있는 격자이다. 

Subtask 4. (34점) 추가 제한 없음. 

5. $1 \le N \le 10^5$개의 울타리가 있다. 

각 울타리는 $xy$ 평면 위의 서로 다른 두 격자점을 잇는 선분 형태로 주어진다. 

이때, 울타리의 양 끝점에 해당되는 격자점의 $x, y$ 좌표는 $-10^9$ 이상 $10^9$ 이하이다. 

한편, 각 울타리의 양 끝점에는 말뚝이 박혀있다. 또한, 각 울타리는 양 끝점이 아닌 점에서 서로 교차하지 않는다. 

마지막으로 울타리 위에 있지 않는 두 점 $S, T$가 주어진다. 

$S, T$를 연결하고, 말뚝을 통과하지 않는 곡선을 긋되, 그 곡선이 울타리와 교차하는 횟수를 최소화하고자 한다.

이 최소값을 구하시오. 단, $S, T$는 울타리 위에 있는 점이 아니고, 말뚝이 박힌 위치도 아님이 보장된다.

시간제한 2초, 배점 100

Subtask 1. (27점) 모든 말뚝은 정확하게 두 울타리와 연결되어 있다. 

Subtask 2. (41점) 임의의 두 말뚝은 울타리를 통하여 연결되어 있다. 

Subtask 3. (32점) 추가 제한 없음.

________________________________________________________________________________________________________________________

대회 진행

일단 대회가 시작하자마자 1번을 열었고, 워낙 전형적인 문제라 바로 코드 작성을 시작했다. 

std::set이나 map 등을 쓰고 싶은 마음이 좀 컸는데, TLE가 뜰 것 같아서 그냥 이진탐색을 짰다.

나중에 들어보니 set/map 쓰고 TLE를 한 번 낸 분이 있었다. 이진탐색 짜는 판단은 잘 한듯.

아직도 이유를 잘 모르겠는 RTE를 한 번 받은 뒤 무난하게 1번을 AC 맞았다. 이때가 시작 후 8분 정도.

그 후 2번을 열었는데, 왜 이 문제가 입시 대비 수학 프린트가 아니라 NYPC에 있는 지 의문이 들었다.  

이거 https://en.wikipedia.org/wiki/Astroid 아님? 그래서 유도도 하지 않고 저 식을 바로 짰다.

pow 함수를 쓰려다가 좀 쫄려서 이진탐색을 돌렸다. 실수오차도 좀 쫄렸지만 바로 AC.

이때 시계를 보니 16분 정도 지났었다. 2번을 빠르게 밀어서 기분이 아주 좋았다. 벌써 유리해진 느낌.

3번을 열어보니 output only 문제였다. 조금 걱정이 앞섰지만, 문제를 읽어보니 풀 수 있을 것 같았다.

만점을 받으려면 핵심 관찰이 하나 쯤은 필요하지 않을까 싶어서 한 30분 정도 고민했는데, 별로 소득이 없었다. 

그래서 우선 긁기로 했다. 먼저 앞에 있는 4가지의 데이터 중 1, 3, 4번은 그냥 손으로 풀어 제출해서 맞았다.  

2번은 손으로 푸는 것과 프로그램을 짜는 것을 섞어서 풀었는데, 그냥 손으로 푸는 게 빨랐을 것 같다. 

5번, 6번을 풀기 위해 데이터를 다운받았는데, 다운받고 보니 그림이 생각보다 간단했다. 

단순 그리디로도 이 두 데이터에서는 만점을 받을 수 있을 것 같아, 다음과 같은 그리디를 고안한 후 짰다. 

Greedy Algorithm 1 (for #3)

1. 먼저 모든 격자를 색깔 $x$로 칠한다.

2. 이제부터 색깔 $x+1$과 ($C=3$인 경우) $x+2$만을 사용한다. 

3. 이제부터 $x$가 아닌 색깔로 칠해진 격자는 다시 칠할 수 없다고 가정한다. 

4. 색칠할 수 있는 직사각형 중 가장 큰 직사각형을 색칠하는 것을 반복한다. 

모든 색깔 index는 적당한 mod를 취해서 보고, $x$는 알고리즘을 돌리기 전에 $1, 2, 3$ 중 하나를 선택한다. 

 

진짜 어마어마하게 비효율적인 알고리즘인데도 5, 6번에서 만점이 나왔다. 조금 예상 밖이었다.  

그래서 7, 8, 9, 10번 데이터를 다운받고 이 알고리즘을 돌려봤는데, 점수가 예상보다 심하게 높게 나왔다. 

7, 8, 9번 데이터에서 10점을 받고 마지막 데이터 10번에서만 9.3점으로, 총 99.3점을 받았다. 

이 시점에서 나는 이 문제에서 $99 + \epsilon$점을 받은 사람이 수두룩 할 것 같았다. 

그래서 이 문제에서 $100$을 받아야 안정적으로 동상을 받을 수 있다고 판단했다. 

이때가 아마 1시간 40분 정도 지났을 시점이었다. 관찰 찾는다고 시간 더 썼으면 많이 말렸을 것 같다. 

$100$점을 지금 바로 노리면 말릴 게 뻔했고, 4, 5번을 읽어보니 긁는 게 엄청 어렵지는 않을 것 같았다. 

그래서 바로 4번을 열었다. $Q$가 20만인 걸 보고 온갖 생각이 다 들었다. 100점 풀이가 가능은 할까?

쿼리를 오프라인으로 답하는 방법을 찾거나, 한 쿼리당 로그로 풀라는 건데, 이게 어떻게 가능할까? 

지나갈 수 없는 격자가 연결되어 있다는 게 뭔 도움이 될까? 문제가 일단 좀 신기했다. 

일단 100점 풀이를 바로 구상하다가는 망할 것 같았고, 풀이가 뻔한 Subtask 1, 2를 짜고 Subtask 3을 고민하기로 결정했다. 

Subtask 1, 2는 그냥 bfs를 돌리면 쉽게 긁을 수 있는 Subtask였고, 구현 실수 2번 끝에 다 맞을 수 있었다. 

Subtask 3은 좀 고민해보니 풀이가 빠르게 나왔다. 직관을 천천히 따라가다 보니 풀이가 바로 나왔다.  

두 점이 대칭축을 기준으로 서로 반대쪽에 있거나, 한 점이 대칭축 위에 있으면 답은 그냥 택시거리다.

결국 두 점이 대칭축을 기준으로 같은쪽에 있는 경우가 중요하다. 

쿼리가 들어온 두 점을 $(sy, sx)$, $(ey,ex)$라 하자. 일반성을 잃지 않고 $sy \le ey$와 $sx, ex \le k$를 가정하자.

$(sy, sx)$, $(ey,ex)$를 잇는 임의의 경로 $P$를 잡고, $P$에 속한 격자의 $x$좌표의 최댓값을 $X$라 하자. 

관찰 1. 조건 1에 의해 중심축이 전부 사용 가능한 격자로 구성되어 있으므로, $X \le k+1$만 고려해도 충분하다.

관찰 2. $X \ge \text{max}(sx,ex)$이고, $\text{length}(P) \ge |ey-sy|+|X-ex|+|X-sx|$이다. 

관찰 3. 조건 2에 의해 $(sy, X), (sy+1,X), \cdots (ey,X)$는 모두 사용 가능한 격자여야 한다. 

관찰 4. 그냥 $(sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)$로 가는 경로를 $P'$이라 하면 $\text{length}(P') = |ey-sy|+|X-ex|+|X-sx|$이다.

관찰 5. 즉, $(sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)$ 꼴 경로만 봐도 무방하다.

관찰 6. $X \ge \text{max}(sx,ex)$면 $|ey-sy|+|X-ex|+|X-sx|$는 $X$에 대한 증가함수다. 

관찰 7. 조건 2에 의해, $X<X' \le k+1$에 대하여 $(sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)$가 가능한 경로면, $(sy, sx) \rightarrow (sy,X') \rightarrow (ey,X') \rightarrow (ey,ex)$도 가능한 경로이다. 

관찰 8. $(sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)$ 꼴 경로가 가능한 최소의 $X \ge \text{max}(sx,ex)$를 찾으면, 답은 $|ey-sy|+|X-ex|+|X-sx|$가 된다. 

관찰 9. 이러한 최소의 $X$는 이진탐색을 통해 찾을 수 있는 형태이다.

관찰 10. 간단한 전처리를 통해 결정문제를 $\mathcal{O}(1)$에 해결할 수 있다. 

이렇게 하면 시간복잡도 $\mathcal{O}(NM+Q\log M)$에 Subtask 3를 풀 수 있다. 총 66점. 

여기까지 하고 일단 5번으로 넘어갔다. 이때가 시험 시작 후 약 2시간 30분 정도 지난 후였다. 

5번은 문제를 읽자마자 dual graph를 생성하면 끝나는 문제임을 파악했다. 문제는 내가 이걸 짤 줄 모른다.

좀 생각해보니 Subtask 2부터는 dual graph를 짤 줄 모르면 절대 못 풀 것 같았고, 그냥 Subtask 1만 긁기로 했다.

Subtask 1에서는 모든 연결 컴포넌트가 하나의 cycle - 즉, 다각형을 이룬다.  

결국 주어진 두 점 $S, T$가 다각형 안에 포함되어 있는지를 선형 언저리 시간에 확인하는 문제로 환원된다. 

이 문제가 풀리면, 두 점 중 하나만 포함하는 다각형의 개수를 세면 답이 되기 때문이다. 이유는 자명.

맨 처음에는 모든 다각형이 볼록이겠거니 싶어서 바로 ccw를 꺼낼 준비를 하고 있었는데, 당연히 아니었다. 

그래서 다각형 내부 판별을 어떻게 할 지 고민을 상당히 오래했다. ccw를 활용하려고 했는데 도저히 길이 없었다. 

결국에는 판별 대상인 점을 지나는 직선 하나를 긋고, 그 직선과 다각형의 변들 사이의 교점을 보는 방식으로 접근했다.   

직선을 그으면, 그 직선은 다각형으로 들어갔다가, 나갔다가, 들어갔다가, 나갔다를 반복한다. 

그러므로 판별 대상 점이 직선 위에서 어느 두 교점 사이에 속하는 지를 찾으면, 다각형 내부 여부를 판별할 수 있다.

직선이 변과 평행하거나 말뚝을 지나게 되면 많이 피곤해진다. 잘 처리하면 Subtask 1을 맞을 수 있다. 27점.

모든 계산을 정수로 한다면, 분자가 최대 $10^{18}$-scale, 분모가 최대 $10^9$-scale로 커지는 분수를 다루게 될 수 있다.

이러한 분수들은 몫을 비교한 뒤, 나머지에 해당하는 분수를 뒤집어서 재귀적으로 비교하는 방식으로 비교할 수 있다.

지금 생각해보면 처리 하나 잘못한 것 같은데 어쩌다가 처리가 잘 된건지 데이터가 물인지 잘 모르겠다 ㅋㅋㅋ

이 시점이 대강 3시간 20분 정도 지났을 때였다. 3번을 100 맞고, 4번 풀이를 고민하기로 했다.

앞서 짠 그리디가 상당히 비효율적임은 자명하다. 그래서 다음과 같이 수정했다. 

Greedy Algorithm 2 (for #3)

1. 일단 만들어야 하는 결과물을 하나 복사해 놓자. 역순으로 본다. 

즉, '이게 다 이렇게 색칠되어 있어야 해'에서 '아무렇게나 색칠되어 있어도 시행하면 결과물이 나오니까 괜찮아'로 간다. 

2. 만들어야 하는 결과물에서, 한 색으로 구성된 가장 큰 직사각형을 찾는다.

3. 그 직사각형을 '맨 마지막'에 색칠한다고 선언한다. 그러면 그 직사각형은 이제 '자유'롭다.

4. 이제 한 색으로 구성된 직사각형을 (자유로운 직사각형도 그 색으로 친다) 다시 찾자.

그 중에서 가장 '자유롭지 않은 격자'의 개수가 많은 직사각형을 찾는다. 그 직사각형은 이제 자유롭다. 

5. 4를 모든 격자가 자유로울 때까지 반복한다. 

이렇게 하면 시행 횟수가 302개가 나와서, 99.95점을 얻을 수 있다. 역겨운 점수다 ㄹㅇ

4에서 우리는 '자유롭지 않은 격자'의 개수가 최대인, 즉 '넓이 - 자유로운 격자 수'가 최대인 직사각형을 선택했다.

이제 적당한 실수 Magic을 잡아서, '넓이 - Magic * 자유로운 격자 수'가 최대인 직사각형을 뽑도록 해보자. 

Magic의 값에 따라서 시행의 횟수가 크게 달라지는데, Magic=1.01을 넣으면 시행 횟수가 296개가 나온다. 

좀 추하긴 했지만 아무튼 3번 100점을 이렇게 얻을 수 있었고, 이때가 3시간 40분이 지났을 때였다. 

4번을 잡았지만 다익스트라 생각에서 벗어나지를 못했다. 너무 어렵다. 나중에 보니 IOI 변형... 

http://blog.myungwoo.kr/20?category=516575 여기에 풀이가 있다. 신기함

그래서 1시간 30분 동안 아무것도 못하고 기도메타를 시전하며 끝났다. 393점 마무리.

고등학생으로 치는 마지막 정보대회를 기분 좋게 끝내서 좋다. 입시도 좀 잘 끝났으면 ㅋㅋ!