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점 마무리.

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