개요
2021 NYPC를 1519 부문 은상이라는 좋은 성적으로 마무리했습니다. 세 번의 예선 탈락 끝에 본선에 진출했는데, 운이 따라 주어서 제 실력보다 매우 높은 상을 받은 듯해 기쁩니다.
예선
올해 예선은 예년과 달리 문제 수가 적어지고 난이도가 쉬워졌습니다. 그래서인지 만점에 가까운 점수를 받아 본선 진출을 확신했습니다.
본선
넥슨 본사에서 네 시간 동안 본선을 치렀습니다. 매우 값진 경험이었고, 온라인상에서만 만나던 친구들을 직접 만날 수 있는 기회도 되었습니다. 모두 280.4점을 받아 은상을 받았습니다.
| 문제 | 1 | 2 | 3 | 4 | 5 | 총점 |
| 점수 | \(100\) | \(100\) | \(15\) | \(41\) | \(24.4\) | \(280.4\) |
타임라인
아래 내용은 정확하지 않을 수도 있습니다.
~ 0:00
NYPC 본선에 무려 N 번 참가한 kizen의 조언으로 미리 준비한 전략은 다음과 같았습니다.
0:00 ~ 1:00: 1번, 2번은 쉬우므로 1번과 2번을 풉니다.
1:00 ~ 2:00: 3번은 풀 만하므로 3번을 풉니다.
2:00 ~ 2:30: 4번은 어려우므로 부분 점수를 받습니다.
2:30 ~ 4:00: 5번은 output only이므로, 열심히 부분 점수를 받습니다.
대회 시작 전 개발 환경을 점검했는데, 평소에 이용하던 Sublime Text가 설치되어 있어서 안도했습니다. 다만 Sublime Text 사용자 분들께서 아시다시피 컴파일을 위해서는 여러 복잡한 설정이 필요합니다. 하지만 제공된 컴퓨터에서는 파일 탐색기에 파일 수정 권한이 없었고, 결국 Sublime Text는 텍스트 에디터로만 사용하고 명령 프롬프트를 이용해 g++ --std=c++14 -O2 -o %i%.exe %i%.cpp & %i%.exe < input.txt를 작성해 컴파일했습니다. g++가 제가 이용하는 C++20은커녕 대회 페이지에서 채점할 수 있는 C++17조차도 지원하지 않아 의아했습니다.
0:00 ~ 0:30: 200점
1번, 2번 문제를 읽고 풀었습니다.
문제 1. 길이 \(n(\leq500\,000)\)의 두 수열 \(A=\{a_i\}\)와 \(B=\{b_i\}\)가 주어집니다. 두 수열에서 연속한 \(k\) 개의 수를 독립적으로 선택한 뒤, 그중 가장 앞의 수를 교환합니다. 두 수열에서 선택된 수들의 합의 차이의 최솟값은 얼마인가요?
풀이: 다음과 같이 \(p_i\), \(q_i\)를 정의합니다.
$$\begin{cases}p_i=-a_i+a_{i+1}+a_{i+2}+\cdots+a_{i+k-1}=\sum_{j=i}^{i+k-1}a_j-2a_i\\q_i=-b_i+b_{i+1}+b_{i+2}+\cdots+b_{i+k-1}=\sum_{j=i}^{i+k-1}b_j-2b_i\end{cases}$$
이제, 구하는 값은 두 정수 \(1\leq i,\,j\leq n-k+1\)에 대하여 \(|p_i-q_j|\)입니다. \(p_i\), \(q_i\) 각각은 누적 합을 이용해 \(O(n)\) 전처리와 \(O(1)\) 시간 안에 구할 수 있습니다. 이는 \(\{p_i\}\)와 \(\{q_i\}\)를 정렬하고 투 포인터를 이용해 해결할 수 있습니다. 시간 복잡도는 \(O(n\log n)\)입니다.
문제 2. 길이 \(n(\leq200\,000)\)의 수열 \(A=\{a_i\}\)와 \(P=\{p_i\}={\sum_{j=1}^ia_j\}\)에 대하여 다음과 같은 시행을 여러 번 할 수 있습니다.
· 정수 \(1\leq i\leq n\)에 대하여 \(a_i\leftarrow0\).
모든 정수 \(1\leq i\leq n\)에 대하여 \(p_i\geq0\)이 되도록 하는 데에 필요한 시행의 최소 횟수는 얼마인가요?
풀이: \(p_1\)부터 \(p_n\)까지의 각 원소를 보면서 다음을 수행합니다.
· \(a_i<0\)이라면, 우선 순위 큐에 \(-a_i\)를 삽입합니다.
· \(p_i<0\)인 동안 우선 순위 큐에서 가장 큰 원소를 빼서 \(p_i, p_{i+1}, \cdots, p_n\)에 더합니다.
우선 순위 큐에서 원소가 빠지는 횟수가 문제의 답입니다. 시간 복잡도는 \(O(n\log n)\)입니다.
0:30 ~ 2:00: 215점
3번 문제를 풀려고 노력했습니다.
문제 3. https://www.acmicpc.net/problem/23347
부분 문제 1(15점): \(2M\leq K\)입니다. \(A\)의 모든 수를 차례로 제거하고 \(B\)의 모든 수를 차례로 삽입할 수 있습니다. \(x(1\leq x\leq K)\)를 제거하기 위해서는, \(x>M\)이면 \(1, 2, \cdots, M\)을 \(x\) 앞에 삽입하고 \(1, 2, \cdots, M, x\)를 제거하며 \(x\geq K-M\)이면 \(K-M+1, K-M+2, \cdots, K\)를 \(x\) 뒤에 삽입하고 \(x, K-M+1, K-M+2, \cdots, K\)를 제거합니다. 삽입은 대칭적으로 동일합니다.
만점 풀이: 만점 풀이는 대회가 끝나고 나서 찾았습니다. 먼저 \(A\)에서 몇 개의 수를 제거하고 \(B\)에서 몇 개의 수를 제거해서 \(A'\), \(B'\)를 만들었을 때 \(A'=B'\)라면, \(A\rightarrow A'=B'\rightarrow B\)와 같이 \(A\)를 \(B\)로 만들 수 있습니다.
- \(M>K\)이면 아무 시행도 할 수가 없으므로 \(A=B\)일 때에만 가능합니다.
- \(M=K\)이면 \(A\)와 \(B\)에서 \(1,2,\cdots,K\)를 탐욕법으로 여러 차례 찾아 제거합니다. 그러한 방법은 유일합니다.
- \(M<K\)이면 \(M=K-1\)로 두고 문제를 풀어도 충분합니다. 이때에는 부분 문제 1의 전략이 조금 더 구성적으로 복잡한 방법으로 성립합니다. 먼저, \(1, 2, \cdots, x\)와 \(K-x+1, K-x+2, \cdots, K\)를 각각 \(2x\) 번의 연산만으로 만들어 낼 수 있습니다. \(x=1\)이면 \(1, 2, \cdots, K\)를 추가한 뒤 \(2, 3, \cdots, K\)를 제거해서 \(1\)을, \(1, 2, \cdots, K\)를 추가한 뒤 \(1, 2, \cdots, K-1\)을 제거해서 \(K\)를 두 번의 연산만으로 만들어 낼 수 있습니다. \(x=k(<K-1)\)일 때 \(1, 2, \cdots, k\)와 \(K-k+1, K-k+2, \cdots, K\)를 \(2k\) 번의 연산만으로 만들어 낼 수 있다고 가정합시다. 그러면 \(1, 2, \cdots, k+1\)은 다음과 같은 방법으로 만들 수 있습니다.
· \(1, 2, \cdots, K\)를 추가합니다. \(1, 2, \cdots, K\)
· \(1, 2, \cdots, k\)를 추가합니다. \(1, 2, \cdots, k+1, 1, 2, \cdots, k, k+2, k+3, \cdots, K\)
· \(1, 2, \cdots, k, k+2, k+3, \cdots, K\)를 제거합니다. \(1, 2, \cdots, k+1\)
마찬가지로, \(K-k, K-k+1, \cdots, K\)도 다음과 같은 방법으로 만들 수 있습니다.
· \(1, 2, \cdots, K\)를 추가합니다. \(1, 2, \cdots, K\)
· \(K-k+1, K-k+2, \cdots, K\)를 추가합니다. \(1, 2, \cdots, K-k-1, K-k+1, K-k+2, \cdots, K, K-k, K-k+1, \cdots, K\)
· \(1, 2, \cdots, K-k-1, K-k+1, K-k+2, \cdots, K\)를 제거합니다. \(K-k, K-k+1, \cdots, K\)
위에서 각각을 만드는 데 든 연산의 횟수는 \(2(k+1)\) 번입니다. 이제 수학적 귀납법을 따라, 혹은 재귀적으로 \(1, 2, \cdots, x\)와 \(K-x+1, K-x+2, \cdots, K\)를 각각 \(2x\) 번의 연산만으로 만들어 낼 수 있습니다.
따라서, \(A\)의 각 원소 \(a_i\)에서 \(1, 2, \cdots, a_i-1\)과 \(a_i+1, a_i+2, \cdots, K\)를 추가하여 \(1, 2, \cdots, K\)를 만들 수 있으므로, \(2K-1\) 회의 연산만으로 \(a_i\)를 제거할 수 있습니다. 이가 \(B\)에서도 마찬가지로 성립하며, \(A\)를 \(B\)로 만드는 데에 필요한 연산의 횟수는 \(2\times K\times(2K-1)\leq4K^2\leq10\,000\)입니다.
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>
#include <utility>
#include <cstdlib>
#include <algorithm>
using namespace std;
int m, k, a, b, dp_a[56], dp_b[56];
vector<int> x, y, t;
vector<pair<char, vector<int>>> res1, res2;
void make_from_begin(int p, int v) {
if (v <= 0) return;
t = { p, k };
for (int j = 0; j < k; j++) t.push_back(j + 1);
res1.push_back({ '+', t }); t.clear();
make_from_begin(p + v, v - 1);
res1.push_back({ '-', { p + v, k - 1 } });
}
void remove_from_begin(int p, int v) {
if (v <= 0) return;
res2.push_back({ '-', { p, k } });
remove_from_begin(p + v, v - 1);
t = { p + v, k - 1 };
for (int j = 0; j < k; j++) if (j != v - 1) t.push_back(j + 1);
res2.push_back({ '+', t }); t.clear();
}
void make_from_end(int p, int v) {
if (v <= 0) return;
t = { p, k };
for (int i = 0; i < k; i++) t.push_back(i + 1);
res1.push_back({ '+', t }); t.clear();
make_from_end(p + k - v, v - 1);
res1.push_back({ '-', { p, k - 1 } });
}
void remove_from_end(int p, int v) {
if (v <= 0) return;
res2.push_back({ '-', { p, k } });
remove_from_end(p + k - v, v - 1);
t = { p, k - 1 };
for (int j = 0; j < k - v; j++) t.push_back(j + 1);
for (int j = k - v + 1; j < k; j++) t.push_back(j + 1);
res2.push_back({ '+', t }); t.clear();
}
int main() {
scanf("%d%d", &k, &m);
scanf("%d", &a);
for (int i = 0; i < a; i++) {
int t;
scanf("%d", &t);
x.push_back(t);
}
scanf("%d", &b);
for (int i = 0; i < b; i++) {
int t;
scanf("%d", &t);
y.push_back(t);
}
if (m >= k) {
next:;
for (int i = 0; i < (int)x.size(); i++) {
if (i && x[i - 1] < x[i]) dp_a[i] = dp_a[i - 1] + 1;
else dp_a[i] = 1;
}
for (int i = 0; i < (int)y.size(); i++) {
if (i && y[i - 1] < y[i]) dp_b[i] = dp_b[i - 1] + 1;
else dp_b[i] = 1;
}
for (int i = (int)x.size() - 1; i >= m - 1; i--) if (dp_a[i] == m) {
for (int j = i; j >= i - m + 1; j--) x.erase(x.begin() + j);
res1.push_back({ '-', { i - m + 1, m } });
goto next;
}
for (int i = (int)y.size() - 1; i >= m - 1; i--) if (dp_b[i] == m) {
for (int j = i; j >= i - m + 1; j--) y.erase(y.begin() + j);
t = { i - m + 1, m };
for (int j = 0; j < m; j++) t.push_back(j + 1);
res2.push_back({ '+', t }); t.clear();
goto next;
}
if ((int)x.size() != (int)y.size()) return puts("NO"), 0;
for (int i = 0; i < (int)x.size(); i++) if (x[i] != y[i]) return puts("NO"), 0;
} else {
for (int i = a - 1; i >= 0; i--) {
make_from_end(i + 1, k - x[i]);
make_from_begin(i, x[i] - 1);
res1.push_back({ '-', { i, k } });
}
for (int i = b - 1; i >= 0; i--) {
remove_from_end(i + 1, k - y[i]);
remove_from_begin(i, y[i] - 1);
t = { i, k };
for (int j = 0; j < k; j++) t.push_back(j + 1);
res2.push_back({ '+', t }); t.clear();
}
}
puts("YES");
printf("%d\n", (int)res1.size() + res2.size());
for (auto &i: res1) {
printf("%c ", i.first);
for (auto &j: i.second) printf("%d ", j);
puts("");
}
reverse(res2.begin(), res2.end());
for (auto &i: res2) {
printf("%c ", i.first);
for (auto &j: i.second) printf("%d ", j);
puts("");
}
}
그 뒤 만점 풀이를 찾았다고 생각하고 3번을 짰지만 장렬하게 WA를 받고 폭사했습니다. 자세한 내용은 알려 드릴 수 없습니다.
2:00 ~ 2:30: 256점
4번 문제에서 부분 점수를 받았습니다.
문제 4. 길이 \(n(\leq200\,000)\)의 수열 \(A=\{a_i\}\)를 연속한 \(K\) 개의 구간으로 나눕니다. 각 구간에서 (최댓값 - 최솟값)의 합을 최소로 하고자 합니다. 각 \(K(1\leq K\leq n)\)에 대하여 그 값은 얼마인가요?
부분 문제 1(18점): \(n\leq300\)입니다. \(a_1,a_2,\cdots,a_i\)를 연속한 \(j\) 개의 구간으로 나누었을 때 최소로 하는 값을 \(dp_{i,\,j}\)라고 할 때, 다음과 같은 점화식을 작성합니다.
$$cost_{i,\,j}=\max_{i\leq k\leq j}(a_k)-min_{i\leq k\leq j}(a_k)$$
$$dp_{i,\,j}=\begin{cases}cost_{1,\,i}&j=1\\0&i=0\\\max_{0\leq k<i}(dp_{k,\,j-1}+cost_{k+1,\,j})&\text{otherwise}\end{cases}$$
각 \(dp_{i,\,j}\)를 계산하는 데에 \(O(n)\) 시간이 걸리니, 전체 \(O(n^3)\) 시간 안에 모든 \(dp_{i,\,j}\)를 계산할 수 있습니다. 시간 복잡도는 \(O(n^3)\)입니다.
부분 문제 2(23점): \(N\leq5\,000\)입니다. 위 점화식을 잘 보면 분할 정복을 이용해 최적화할 수 있습니다. 시간 복잡도는 \(O(n^2\log n)\)입니다.
\(O(n^2)\) 풀이(benedict0724): 점화식을 다른 방법으로 세웁니다. 구하는 값을 각 구간에서 최댓값을 더하고 최솟값을 뺀 것으로 생각할 수 있습니다. 따라서 각 수를 순회하며 더한 수가 뺀 수보다 하나 많은 상황, 더한 수와 뺀 수의 개수가 서로 같은 상황, 그리고 더한 수가 뺀 수보다 하나 적은 상황의 세 가지 상태를 유지하며 항들을 갱신할 수 있다고 합니다.
2:30 ~ 3:00: 256점
헛된 발버둥이었지마는 3번 문제를 풀려고 노력했습니다. 당시에는 누구 때문인지 300점 이상 받아야 수상할 수 있을 줄로 알았던지라, 누구나 다 풀었을 듯한 3번을 잡았습니다. 하지만 풀지 못했습니다.
3:00 ~ 4:00: 280.4점
당연히 output only 문제일 줄 알았던 5번 문제를 읽고 output only가 아니라서 당황했습니다.
문제 5. 초기에 \((0,0)\)에 위치한 로봇 청소기에 \(n(\leq250\,000)\) 개의 명령이 주어져 있습니다. 각 명령은 \(\text{U} x\), \(\text {R} x\), \(\text{D} x\) 중 하나로, 각각 로봇 청소기가 위로 \(x\)만큼, 오른쪽으로 \(x\)만큼, 밑으로 \(x\)만큼 이동하라는 명령입니다.(\(1\leq x\leq8\,000\)) 단, 로봇 청소기는 설치되어 있는 \(N\) 개의 장애물과 마주하면 더 이상 이동하지 못하고 다음 명령을 이어서 수행합니다. 로봇 청소기의 최종 위치가 될 수 있는 위치의 개수는 얼마인가요? 또한, \((X,Y)\)에 로봇 청소기가 도달하기 위해 설치해야 하는 장애물의 위치는 얼마인가요?
부분 문제 1(8점): \(N\leq6\), \(x\leq10\)입니다. 각 명령에 대해 장애물을 설치할 수 있는 위치는 설치하지 않는 경우를 포함해 열한 가지이므로, \(11^6\) 가지의 경우에 대해 모두 계산해 볼 수 있습니다. 시간 복잡도는 \(O((x+1)^NNx)\)입니다.
부분 문제 2(6.4점/16점): 가능한 명령은 \(\text{U} x\), \(\text{D} x\)밖에는 없습니다. 장애물이 없을 때 로봇 청소기가 지나는 최대의 \(y\)좌표 \(y_\text{max}\)와 최소의 \(y\)좌표 \(y_\text{min}\)에 대하여 \(y_\text{max}-y_\text{min}+1\)입니다.
부분 문제 2(benedict0724): \(X\neq0\)이거나 \(Y>y_\text{max}\) 또는 \(Y<y_\text{min}\)이면 가능한 경우가 없습니다. 그렇지 않으면 장애물을 최대 하나 설치해서 \((X,Y)\)로 이동할 수 있습니다. 최종 \(y\)좌표와 \(Y\)만큼의 차이를 유일한 장애물로 막으면 된다고 합니다.
부분 문제 3(10점): 가능한 명령은 \(\text{U} x\), \(\text{R} x\)밖에는 없습니다. 장애물이 없을 때 로봇 청소기의 최종 좌표 \((x,y)\)에 대해 \((0,0)\)과 \((x,y)\)을 두 꼭짓점으로 하는 직사각형상의 경계를 포함한 모든 위치에 로봇 청소기가 위치할 수 있습니다. 구체적으로, 각 명령에 대해 로봇 청소기가 이동하는 좌표 \((x',y')\)에서 \(x'>x\)이거나 \(y'>y\)일 때만 로봇 청소기가 더 멀리 가지 못하도록 장애물로 막으면 됩니다.
부분 문제 2를 대회 종료를 1분 남긴 시점에 40%의 점수만 받았습니다. 나머지 60%를 생각했다면 또 상황이 달라졌겠죠. 상당히 아쉽습니다.
4:00 ~
시상식이 있었습니다. 저는 동상을 목표로 했기에 그 당시에 낮다고 생각했던 점수만으로도 동상을 받을 수 있으리라 내심 기대했습니다마는 동상에 이름이 불리지 않아 실망하던 찰나에 은상을 수상하게 되어서 어리둥절하면서도 기쁜 마음을 숨길 수 없었습니다. 한 번의 충격 이후 대상의 정체에서 다시 한번 놀랐습니다. "경기과학고등학교 ㅊ……." 여기까지 하겠습니다.
총평
정말이지 예상하지 못한 결과였습니다. 제 실력으로는 동상도 어려울 거라고 생각해 동상을 목표로 잡았는데 은상이라니요. 잘하시는 여러 분들께서 여러 이유로 숱하지 않게 고전하신 까닭에 수상하게 된 것으로 생각합니다. 다만 제가 알기로 대상의 점수는 282점입니다. 282점에 대상이라니, NYPC는 빈집인가요? 아무래도 여느 대회가 그렇듯이 저와 점수 차가 적은 까닭에 아쉬움이 남습니다. 이번 NYPC는 코로나19 대유행으로 PS를 하는 친구들끼리 만나기 어려운 상황에서 서로 얼굴을 볼 수 있었던 귀한 기회였습니다. NYPC에서는 참가상이 음수인 어떤 대회와 달리 대우를 몹시 잘해주더군요. 관계자 분들께 좋은 대회를 준비해 주셔서 감사하다는 말씀을 다시 한번 드리고 싶습니다.
