개요
2023 NYPC가 2라운드의 예선전과 본선전을 거쳐 10월 29일에 마무리되었습니다. 세 번째 NYPC 본선 참가로 제가 대회에 참가할 수 있는 마지막 기회였습니다만, 대상으로 마무리할 수 있어서 무척 기쁩니다. 대회에서의 경험을 기록하고자 합니다.
본선
판교 넥슨코리아에서 네 시간 동안 대회를 치렀습니다. 작년, 재작년보다도 대회 규모가 크게 확대되어 1519 부문에는 60명이 참가했습니다. 또, 문제를 해결할 때마다 책상에 풍선을 달아 주어 분위기가 훨씬 좋았습니다. 모두 484점으로 대상을 받았습니다.
| 문제 | 1 | 2 | 3 | 4 | 5 | 총점 |
| 점수 | 100 | 100 | 100 | 100 | 84 | 484 |
타임라인
~ 0:00:00
NYPC 대회장 앞에서 windva, DELTARUNE, Kawaii2DIdolOfGSHS, Faruzan, Equinox_ 등을 만나서 대회장에 들어갔습니다. windva가 신분증을 지참하지 않아서 탈락하길 바랐는데 그렇게 되지는 않았습니다. 대회가 시작하기 전에 사전 점검을 했는데, IDE는 항상 사용하던 Sublime Text를 사용했습니다. g++를 이용해 컴파일하는 데 잠깐 문제가 있었는데, 스태프 분께서 해결해 주셨습니다.
0:00:00 ~ 0:14:56 (100점)
1번 문제를 읽고 해결했습니다.
처음에 문제를 읽고 값이 0인 포탈이 새로 생기거나 없어지지 않는다는 조건을 보지 못해서 어려운 문제인 줄 알았습니다. 다행히 조건을 나중에 보고 문제를 해결했습니다. 먼저 값이 0인 포탈이 고정되어 있으므로, std::set에 값이 0인 포탈의 각 위치 \(i\)와 \(N+i\)를 저장합니다. 이렇게 하면 값이 \(X\)인 포탈의 위치가 주어질 때마다, 그것 이상이면서 가장 작은 값을 std::set에서 빠르게 찾을 수 있습니다. 쿼리가 주어질 때마다 이렇게 얻은 '난이도'들을 std::multiset에, 그리고 이것들을 xor한 값을 관리합니다. 이렇게 하면 난이도들의 최댓값, 최솟값, 그리고 xor한 값을 모두 빠르게 관리할 수 있습니다. 이로써 100점을 받을 수 있습니다. 시간 복잡도는 \(O((N+Q)\log N)\)입니다.
0:14:56 ~ 0:20:47 (200점)
2번 문제를 읽고 해결했습니다.
\(S_1=0\), \(S_j=\sum_{i=1}^{j-1}A_i\)라고 정의합니다. 목표는 수열 \(A_i\)의 값을 1씩 바꾸어 어떤 상수 \(k\)에 대하여 \(k+S_i\)가 되도록 하는 것입니다. 다르게 생각하면, \(A_i-S_i\)의 값이 일정하게 되도록 해야 합니다. 수직선에 \(N\) 개의 점을 \(A_i-S_i\) 위치에 그리고, 모든 점으로부터의 거리의 합이 최소가 되는 점을 찾습니다. 그러한 점 \(x\)는 \(A_i-S_i\)를 오름차순으로 정렬했을 때, \(\lfloor\frac{N+1}{2}\rfloor\)째 수부터 \(\lfloor\frac{N}{2}\rfloor+1\)째 수까지의 사이에 있는 모든 수입니다. 따라서, \(\lfloor\frac{N+1}{2}\rfloor\)째 수까지의 거리의 합이 답이 됩니다. 이로써 100점을 받을 수 있습니다. 시간 복잡도는 수들을 정렬하는 시간인 \(O(N\log N)\)입니다.
여기까지 풀고 나서 스스로 꽤 빠르다고 생각했는데, 가장 빠른 것은 아니었습니다. 주변에 두 문제를 푼 사람이 몇 명 있었고, 대회 초반이라 풍선을 달아 주는 속도가 문제를 푸는 속도를 따라잡지 못해, 아마 이 시점에 두 문제를 푼 사람이 꽤 있었을 것입니다.
0:20:47 ~ 0:48:27 (213점)
3번 문제를 읽고 부분 점수 13점을 받았습니다.
문제의 \(N\) 제한 조건이 \(N\leq 3\ 000\)인 것을 보고 동적 계획법을 사용하기로 했습니다. \(f_{i,\ j,\ k}\)를 \(A\)의 부분 문자열 \([i, j]\)를 나누었을 때, \([i, N]\)에서 조건에 맞게 만들 수 있는 부분 문자열의 최대 개수로 정의합니다. 이때 \(k\)의 값이 0이면 한 차례의 예외를 허용함을, 1이면 한 차례의 예외도 허용하지 않음을 나타냅니다. 또한, \(g_{i,\ j}\)를 부분 문자열 \([j+1, k]\)의 값이 부분 문자열 \([i, j]\)의 값보다 엄격하게 작은 최대 \(k\)의 값으로, 그러한 \(k\)가 존재하지 않는다면 \(j\)의 값으로 정의합니다. 이제 다음 식이 성립합니다.
$$f_{i,\ j,\ 1}=1+\min_{k>1+g_{i,\ j}}(f_{j+1,\ k,\ 1})$$
$$f_{i,\ j,\ 0}=\min\left(f_{i,\ j,\ 1}, 1+\min_{k>1+g_{i,\ j}}(f_{j+1,\ k,\ 0}), 1+\min_{k>j}(f_{j+1,\ k,\ 1})\right)$$
이것을 빠르게 계산하는 방법은 다음과 같습니다.
- \(g_{i,\ j}\)의 값은 문자열 해싱과 이분 탐색을 통해 값 하나에 \(O(\log N)\) 시간 안에 구할 수 있습니다. 해싱 값을 비교하여 \(A_{i+l}\)과 \(A_{j+1+l}\)의 값이 서로 다른 가장 작은 \(l\)의 값 \(k\)을 이분 탐색으로 구한 뒤, \(A_{i+k}\)의 값과 \(A_{j+1+k}\)의 값의 대소를 비교합니다. 이것을 먼저 전처리합니다.
- 그다음으로 필요한 값들의 형태는 \(\min_{l\geq j}(f_{i,\ l,\ k})\) 형태입니다. \(h_{i,\ j,\ k}=\min_{l\geq j}(f_{i,\ l,\ k})\)로 두면, \(h_{i,\ j,\ k}\)의 값은 \(f_{i,\ j,\ k}\)의 값을 계산하는 과정에서 함께 구할 수 있습니다. 따라서 값 하나에 \(O(1)\) 시간이 걸립니다.
문제의 답은 \(f_{i,\ j,\ 0}\)의 최솟값입니다. 그러나 이것을 구현하면 13점밖에 받지 못합니다. 그 까닭은 부분 문자열에 '0'이 포함된 경우를 고려하지 않았기 때문입니다. 시간 복잡도는 \(g_{i,\ j}\)의 값을 모두 구하는 시간인 \(O(N^2\log N)\)입니다.
0:48:27 ~ 1:06:12 (300점)
3번 문제를 해결했습니다.
여러 가지 반례를 시도해 보다가, 부분 문자열에 '0'이 포함된 경우 위의 방법으로는 \(g_{i,\ j}\)의 값을 정확하게 구할 수 없다는 것을 알게 되었습니다. 그렇기 때문에 몇 가지 예외 처리가 필요합니다.
- \(A_{i}=\text{‘0'}\)인 경우, \(g_{i,\ j}=g_{i+1,\ j}\)입니다.
- \(A_{j+1}\)부터 연속한 '0'의 개수가 \(k\)일 때, 이분 탐색 시 \(A_{i+l}\)과 \(A_{j+1+l}\)의 값을 비교하는 것이 아니라, \(A_{i+l}\)과 \(A_{j+k+1+l}\)의 값을 비교해야 합니다.
이로써 100점을 받을 수 있습니다. 시간 복잡도는 마찬가지로 \(O(N^2\log N)\)입니다.
kizen의 \(O(N^2)\) 풀이입니다. \(g_{i,\ j}\)의 각 값을 \(O(\log N)\) 시간 안에 구하는 대신, 모든 \((i, j)\) 쌍에 대하여 부분 문자열 \([i, N-1]\)과 \([j, N-1]\)의 최장 공통 접두사의 길이를 전처리해 두면 \(g_{i,\ j}\)의 각 값을 \(O(1)\) 시간 안에 구할 수 있습니다. 이렇게 하면 시간 복잡도가 \(O(N^2)\)가 됩니다.
이때 세 문제를 푼 사람이 몇 명 있었고, 3번을 풀지 않고 4번부터 푼 사람도 있었습니다. 시간도 많이 남아서, 이대로 간다면 수상권에 들 수 있으리라고 생각했습니다.
1:06:12 ~ 1:25:15 (400점)
4번 문제를 읽고 해결했습니다.
수평 선분이 레이저에 의해 제거되는 횟수는 최대 수평 선분의 개수인 \(N\) 회입니다. 따라서 각 레이저에 의해 제거되는 수평 선분이 무엇인지를 빠르게 구할 수 있으면, 이 시행을 최대 \(O(N+M)\)회 하게 되므로 문제를 해결할 수 있습니다. 이를 위해서는 세그먼트 트리의 아이디어를 사용합니다. 먼저 모든 \(L_i\)와 \(X_j\)를 모아 좌표를 압축하면, \(x\)좌표 범위는 1부터 \(N+M\)까지가 됩니다. 각 정점이 std::set인 세그먼트 트리를 구성합니다. \([l, r]\)에 대응하는 정점은 \(x\)좌표 범위 \([l, r]\)를 완전히 포함하는 수평 선분의 목록을 담고 있습니다. 이러한 세그먼트 트리의 구성은 각 수평 선분의 \(x\)좌표 범위를 \(O(\log(N+M))\) 개의 세그먼트로 나누게 되므로, 각 수평 선분을 \(O(\log(N+M)\log N)\) 시간 안에 세그먼트 트리에 삽입할 수 있습니다.
이제 각 레이저에 의해 제거되는 수평 선분이 무엇인지 결정합니다. 이것은 레이저의 \(x\)좌표 값 \(X_i\)를 포함하는 \(O(\log(N+M))\) 개의 세그먼트에서 각각 \(y\)좌표 값에 대한 이분 탐색을 통해 마찬가지로 \(O(\log(N+M)\log N)\) 시간 안에 수행할 수 있습니다. 또한, 결정한 수평 선분은 삽입할 때와 같은 방법으로 \(O(\log(N+M)\log N)\) 시간 안에 제거할 수 있습니다. 이로써 100점을 받을 수 있습니다. 시간 복잡도는 \(O((N+M)\log(N+M)\log N)\)입니다.
cherry_hwan의 \(O((N+M)\log(N+M))\) 풀이입니다. 수평 선분과 레이저를 모두 함께, \(y\)좌표를 기준으로 정렬합니다. 이것들을 \(y\)좌표가 증가하는 순으로 보면서 스위핑합니다. 또한, 레이저의 번호를 나타내는 최소 세그먼트 트리를 관리합니다. 현재 요소가 레이저라면, \(x\)좌표에 해당하는 세그먼트 트리의 값을 레이저의 번호 \(i\)로 바꿉니다. 현재 요소가 수평 선분이라면, \(x\)좌표의 범위에서 세그먼트 트리로 최솟값을 찾습니다. 그 최솟값이 자신이 파괴당하게 되는 레이저의 번호 \(k\)가 됩니다. \(P_k\)를 1 감소시키고, 이 값이 0이라면 세그먼트 트리에서 \(k\)를 제거합니다. 이렇게 각 레이저가 파괴하는 수평 선분이 무엇인지 알 수 있으므로, 문제를 해결할 수 있습니다. 이렇게 하면 시간 복잡도가 \(O((N+M)\log(N+M))\)이 됩니다.
4번 문제를 풀고 나서 주변을 보니 4문제를 푼 사람은 저와 kizen뿐이었습니다. 4번 문제까지 쾌속으로 푼 적은 처음이기에 좋았고, 5번 문제가 어렵다면 은상 이상을 탈 수 있으리라고 생각했습니다. kizen이 400점을 받은 지 조금 시간이 지난 시점이라, 저는 안전하게 5번에서 차례로 부분 점수를 받기로 했습니다. 동점자 발생 시 그 점수에 먼저 도달한 사람이 높은 순위가 되기 때문입니다.
1:25:15 ~ 1:29:58 (404점)
5번 문제를 읽고 부분 점수 4점을 받았습니다.
두 점을 연결하는 최단 도로망은 \(x\)좌표나 \(y\)좌표가 서로 같을 때 직선, 서로 다를 때 기역 자 형태입니다. 이를 그대로 구현하면 4점을 받습니다.
1:29:58 ~ 1:42:48 (410점)
5번 문제에서 부분 점수 6점을 추가로 받았습니다.
세 점을 연결하는 최단 도로망은 두 점을 선택해 어떠한 방식으로 연결하고, 남은 점을 도로망에 추가로 연결하는 것입니다. 경우의 수가 많지 않으므로 모든 경우를 시도해 보면 \(N=2\)와 더불어 10점을 받습니다.
1:42:48 ~ 2:08:00 (422점)
5번 문제에서 부분 점수 12점을 추가로 받았습니다.
\(X_i \leq 4\), \(Y_i \leq 4\)라면, 놓을 수 있는 도로의 수는 24입니다. \(2^{24}\) 가지의 모든 경우를 시도하여, 각 경우에서 모든 도로가 연결되어 있고 모든 도시를 지나는지 결정합니다. 이로써 12점을 받습니다.
이 시점에 저는 kizen이 먼저 422점에 도달했을 것이라고 생각했고, 실제로 그렇게 되어 이 시점에 2등이었습니다.
2:08:00 ~ 3:04:51 (450점)
5번 문제에서 부분 점수 25점을 추가로 받았습니다.
그다음 부분 문제는 \(X_i\leq 4\)입니다. 곧, 격자가 가로로 긴 형태입니다. 이것을 보면 Connection Profile DP가 먼저 떠오릅니다. 구현이 복잡하고 까다로워 kizen은 이것을 실제로 구현하기로 결정하기까지 오래 걸렸다고 합니다. 저는 색깔 미로를 출제하는 등 Connection Profile DP를 여러 차례 구현해 봤기 때문에, 바로 구현을 시작했습니다. Connection Profile DP는 이전 \(w\) 개의 격자의 연결 상태에 대한 정보를 저장하며 상태를 전이하는 동적 계획법입니다. 이 문제에서는 도로망의 연결 요소 개수가 하나여야 한다는 조건이 있기 때문에 이것으로 문제를 풀 수 있습니다. 격자의 너비가 짧아야 한다는 요구 사항이 있지만, 이 부분 문제에서는 \(X_i\leq 4\)로 너비가 짧습니다. 구현체를 여러 차례 디버깅해 한 시간쯤 뒤에 50점을 받을 수 있었습니다.
이 시점에 저는 Connection Profile DP의 구현이 복잡하고 까다롭기 때문에 저와 kizen을 제외한 다른 사람들은 450점에 도달하지 못할 것이라고 생각했습니다. 또한 많이 구현해 본 저보다 Connection Profile DP를 더 빨리 짤 수 있는 사람은 없으므로 대상 수상도 가능하겠다고 생각했습니다. 그러나 kizen이 저보다 빨리 400점에 도달했기 때문에, 먼저 450점에 도달했을 가능성이 있었습니다. 왜냐하면 kizen은 지난 며칠간 랜덤 다이아 디펜스를 하며 Connection Profile DP 문제를 풀어서 왔기 때문입니다. 실제로는 kizen은 저보다 몇 분 늦게 450점에 도달해서, 이 시점에 제가 이미 1등이었다고 합니다.
3:04:51 ~ 3:54:44 (484점)
5번 문제에서 부분 점수 34점을 추가로 받았습니다.
좌표 압축을 하면, \(N\)의 제한이 곧 너비, \(x\)좌표의 제한입니다. 추가 득점을 위해서는 Connection Profile DP를 어떻게든 돌게 하는 것 말고는 방법이 없다고 생각했기에, 무모하지만 \(N\leq 12\)에서 다음과 같이 가지치기를 통해 Connection Profile DP를 돌리려고 했습니다.
- 두 축을 기준으로 좌표 압축을 한 후, 더 짧은 쪽을 기준으로 Connection Profile DP를 수행했습니다.
- 도로망이 기존의 가지에서 새로 뻗어 나가는 경우, 그 방향에 도시가 하나 이상 있어야 허용되도록 했습니다.
다행히 이와 같은 최적화로 \(N\leq 12\)에서 Connection Profile DP가 통과되었고, 84점을 받았습니다. 그리고 이 시점에서 484점을 넘는 유일한 방법은 500점을 받는 것인데, 다섯 문제를 풀어 모든 풍선을 단 사람이 없었기에 대상을 확신했습니다.
3:54:44 ~ 4:00:00
5분 안에 점수를 더 올리는 것은 불가능하기에 제출 기록을 보고 타임라인을 기록하며 시간을 보냈습니다.
나중에 알게 된 사실이지만, 5번 문제의 정해는 논문입니다.
그 이후
대회장에서 예상했던 대로 대상을 수상했습니다. 대회가 끝나고 나서 친구들에게 점수를 물었는데, 더 높은 점수는 없었습니다. 이번 대회에서 높은 상을 받고 싶었지만 대상까지는 기대하지 않았는데, 가능한 최적의 시나리오로 대상을 수상해 이보다 더 기쁠 수 없었습니다. 더군다나 이번이 NYPC에 출전할 수 있는 마지막 기회였는데, 대상으로 마무리를 가장 멋있게 장식할 수 있어 더욱 값지게 느꼈습니다.
막내와 부모님께서는 올해부터 동반인 입장이 허용되기도 했고, 이번에 제 마지막 NYPC 출전인 만큼 함께 오셔서 대회장 밖에서 기다리셨는데, 대회 종료 30분 전까지 제가 450점으로 1등이었노라고 알려 주셔 대상 수상이 확실시되었습니다. 이후 매년 그렇듯 시상식이 진행되었습니다. 친구들이 차례로 호명되었는데, 저는 제가 대상을 수상했다는 것을 이미 알고 있어 크게 떨리지는 않고 그저 기뻤습니다. 그리고 제 차례가 오자 시상대로 나갔는데, 생각했던 것보다 말하기가 어렵고 몸도 굳어서 움직이지 않았습니다. 소감 발표에서는 가장 먼저 "감사합니다."로 운을 뗀 뒤 대상 받을 실력이 아니지만 문제가 제게 유리하게 출제되었노라고 말했는데, 거짓말이 아닙니다.
이후 1214 부문에서 대상을 수상한 15631164와 함께 기자 분들과 질답도 하고 모두가 떠난 대회장을 배경으로 인터뷰도 했는데, 인생에 얼마 없을 귀한 경험이었지만 힘든 시간이기도 했습니다. 이것을 모두 끝내자 친구들은 이미 저녁을 먹으러 떠난 상황이었습니다. 부모님께서 고맙게도, 친구들과 노는 동안 기다리겠노라고 말씀하셔서 저도 친구들과 합류해 작년, 재작년처럼 놀았습니다.
총평
전혀 기대하지 못한 대상을 받게 되어 몹시 기쁘고 감사합니다. 제가 NYPC를 처음 알게 된 것은 중학교 1학년 때였고, 그때부터 참가해 고등학교 1학년 때 처음으로 본선에 진출했습니다. 그때에는 제가 NYPC에서 대상을 받으리라고는 꿈도 꾸지 못했고, 역대 NYPC 대상 수상자들은 제 우상이었습니다. 그런데 제가 대상 수상이라니, 아직까지도 믿어지지 않습니다. 다시 한번 고맙습니다.
이번 대회는 지난 대회보다 규모가 커지고, 풍선 시스템도 도입해 분위기가 살아난 느낌이었습니다. 또한 본선 대회의 문제는 1번부터 4번까지의 난이도가 낮은 반면 5번 문제는 만점을 받기가 매우 어려웠고, 저도 그 덕에 대상을 받을 수 있었습니다. 지난 6년 동안 NYPC는 제가 PS를 계속할 수 있었던 동기이자 가로등이 되었고, 또 제가 자신감을 가질 수 있도록 도와주기도 했습니다. 세 차례의 수상은 하나하나가 몹시 귀한 경험이었고, 올해 대회는 앞으로 절대 잊지 못할 것입니다. 비록 저는 더 이상 NYPC에 출전할 수 없지만, 앞으로도 NYPC가 계속되어 PS를 하는 많은 친구들에게 기쁨을 주면 좋겠습니다.
