IOI 2022 Day 1

IOI 2022 Day 1 대회가 종료되었다. 올해 대회의 개최지는 인도네시아에서 진행하며, 온라인 대회 역시 병행한다. 한국 팀은 온라인 참가를 결정하였기 때문에, 현재 서울에서 모여서 감독 하에 대회를 진행하고 있다.

한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.

• 장태환, 100 / 53 / 58, 211점, 27등
• 반딧불, 53 / 80 / 58, 191점, 37등
• 조영욱, 67 / 51.5 / 58, 176.5점, 44등
• 박상훈, 70 / 72 / 27, 169점, 50등

예년과 대비했을 때 성적은 대략 평이한 수준이고, 학생들의 점수대는 그렇게 높지도 않지만 금메달을 받기 힘들 정도로 점수가 벌어진 학생도 없다. 보통 한국 학생들의 성적이 Day 2에서 잘 나오는 편인데, 올해도 그러한 결과가 나온다면 좋은 성적을 기대할 수 있을 것 같다.

중국은 IOI 2021, IMO 2022에서도 각 대회 역사상 최고의 성적을 거두었기에, 이번에도 아주 좋은 성적을 얻을 것이 예상되었다. Day 1 기준, 사전 예상과 동일하게 모든 학생이 만점을 얻었다. 중국 학생들의 뒤를 따라, 미국의 Hankai Zhang 학생이 280점, 캐나다의 Zixiang Zhou 학생이 277점을 받았다.

Day 1 Problems PDF

fish-en_ISC.pdf

0.18MB

fish-ko_KR.pdf

0.28MB

notice-en_ISC.pdf

0.15MB

notice-ko_KR.pdf

0.23MB

prison-en_ISC.pdf

0.18MB

prison-ko_KR.pdf

0.32MB

towers-en_ISC.pdf

0.20MB

towers-ko_KR.pdf

0.30MB

구현한 코드는 https://github.com/koosaga/olympiad/tree/master/IOI 에 모두 올라와 있다.

문제 1. 메기 농장

서브태스크 1 (3점)

$X$ 좌표가 홀수인 모든 지점에 길이 $N$ 의 낚시터를 설치하면, 모든 메기를 잡을 수 있다. 답은 $W[i]$ 의 합이다.

서브태스크 2 (9점)

$X = {0, 2, \ldots}$ 인 지점에 길이 $N$ 의 낚시터를 설치하면 $X[i] = 1$ 인 메기를 모두 잡을 수 있다. $X = 1$ 인 지점에 길이 $N$ 의 낚시터를 설치하면 $X[i] = 0$ 인 메기를 모두 잡을 수 있다.

$N = 2$ 일 때는 $X[i]$ 가 다른 메기를 동시에 잡을 수 없기 때문에, 둘 중 하나의 선택을 하면 된다.

$N > 2$ 일 때는 $X = 2$인 지점에 낚시터를 설치한다고 다른 메기를 잡지 못하게 되는 일이 없다. 또한, $X = 2$ 인 지점에 낚시터를 설치했다면 $X = 0$ 인 지점에 낚시터를 설치할 이유가 없다. 고로 $X = 1$ 인 지점에 설치하는 낚시터의 길이만 적절히 조절해 주면 된다. 각 길이에 대해서 잡을 수 있는 메기의 수가 부분합 형태로 계산 가능하여, 모든 길이를 시도해 보면 된다.

서브태스크 4 (32점)

서브태스크 $3, 4$ 에서는 $Y$ 좌표의 제한이 작다는 점을 활용한다. (서브태스크 3은 조금 더 간단한 DP 풀이가 있으나 굳이 설명하지 않는다.)

$h[i]$ 를 $i$번 열에 설치한 낚시터의 길이라고 하자 ($h[-1], h[N]$ 등은 모두 $0$ 으로 간주한다). 낚시터의 길이가 고정되어 있을 때, 위치 $(i, j)$ 에 있는 메기가 잡힌다는 것은, $h[i] \leq j < max(h[i - 1], h[i + 1])$ 를 만족한다는 것과 동치이다. 이를 토대로 DP를 할 수 있다.

$DP[i][k][j]$ 를, $h[i - 1] = k, h[i] = j$ 일 때, $0 \ldots i - 1$ 번 열에서 잡은 메기의 무게 합 최대라고 정의하자. 모든 가능한 $h[i - 2] = l$에 대해서 상태 전이를 하는데, 이 때의 가중치는 $DP[i - 1][l][k]$ 에, $i - 1$ 번 열에서 잡게 될 메기의 무게 합을 더한 값이 된다.

$i - 1$ 번 열에서 잡게 될 메기는 $[k, max(l, j))$ 행 구간에 존재한다. 이 영역의 무게 합은 초기 전처리 후 $O(1)$ 에 계산할 수 있다. 이 계산 결과를 통해서 상태를 전이한다.

시간 복잡도는 $O(N Y^3)$ 이다.

서브태스크 5 (53점)

서브태스크 4의 풀이를 약간 더 개선하면 된다. $DP[i][k][j]$ 의 상태 전이를 수식으로 풀어서 명확하게 해 보자. $S[i][j]$ 를, $i$ 번 열의 $[0, j - 1]$ 번 행에 존재하는 메기의 무게 합이라고 하면

$DP[i][k][j] = \max_{l} DP[i - 1][l][k] + max(0, S[i - 1][max(l, j)] - S[i - 1][k])$

이라는 식이 도출된다. 이는 풀어서

$DP[i][k][j] = max(\ \max_{l} DP[i - 1][l][k], \ \max_{l} DP[i - 1][l][k] + S[i - 1][max(l, j)] - S[i - 1][k])$

라고 쓸 수 있다.

이 중 $\max_{l} DP[i - 1][l][k]$의 경우, $(i, k)$ 에 고정된 상수이기 때문에, 한 번만 단순 반복문을 돌려주면 쉽게 계산할 수 있다. 고로 두 번째 항을 보자. 두 번째 항의 경우 두 가지 케이스가 있다.

• Case 1. $l \le j$. 이 경우 $\max_{l \le j} DP[i - 1][l][k] + S[i - 1][l] - S[i - 1][k]$ 를 계산하면 된다. $(i, k)$ 가 고정된 경우 위 식은 Prefix max의 형태를 띈다. $j$ 를 증가하면서, $l = j$ 일 때의 경우를 갱신해 주는 것을 반복하는 식으로 값을 관리할 수 있다.
• Case 2. $l > j$. 이 경우 $\max_{l > j} DP[i - 1][l][k] + S[i - 1][j] - S[i - 1][k]$ 를 계산하면 된다. $(i, k)$ 가 고정된 경우 위 식은 Suffix max의 형태를 띈다. $j$ 를 감소하면서, $l = j+1$ 일 때의 경우를 갱신해 주는 것을 반복하는 식으로 값을 관리할 수 있다.

이를 통해 각 항을 $O(1)$ 시간에 채울 수 있다. 전체 상태가 $O(N^3)$ 개이니, 시간 복잡도는 $O(N^3)$ 이다.

만점 풀이

서브태스크 5에서의 DP 풀이가 만점을 받기에는 너무 무겁기 때문에, 몇 가지 관찰을 통해서 구조를 제약시키고, 더 단순한 DP를 얻는 것이 목표이다.

각 열을 낚시터가 있는 경우와 없는 경우로 분리할 수 있는데, 이 중 낚시터가 있는 연속된 열 구간들을 컴포넌트 라고 정의하자. 즉, 컴포넌트 구간 $[L, R]$ 안에 속하는 열들은 모두 길이 1 이상의 낚시터가 있고, 구간의 양 끝 밖 ($L - 1, R + 1$) 에 있는 열들은 낚시터가 없다.

이렇게 각 열들을 컴포넌트로 묶게 될 경우 좋은 성질들을 관찰할 수 있다. 첫 번째로, 컴포넌트를 이루는 낚시터의 길이는 계곡 을 이루는 경우가 없다. 만약 컴포넌트 안의 낚시터의 길이가 $a > b < c$ 와 같이, 중간에 있는 원소가 양 끝 인접한 원소보다 작은 경우가 있다고 하자. 이 경우, $b = 0$ 으로 두어서, 중간에 있는 낚시터를 아예 없앨 경우, 더 많은 메기를 잡을 수 있다. 고로 최적해에서는 이러한 경우가 없다고 가정할 수 있고, 이것은 낚시터의 길이를 순서대로 봤을 때, 낚시터의 길이가 증가하다가 감소하는 수열 의 형태를 띈다는 것을 뜻한다.

어떠한 컴포넌트 $[L, R]$ 의 최댓값이 $X$ 에 형성되어 있다면, $[L - 1, X - 1]$ 구간에서 우리는 $Y[i]$ 가 우상향하는 방향으로 메기를 잡을 수 있고, $[X + 1, R + 1]$ 구간에서 우리는 $Y[i]$ 가 우하향하는 방향으로 메기를 잡을 수 있다. 저 문제는 조금 더 쉬워 보이니, 저러한 쉬운 문제를 컴포넌트마다 독립적으로 해결하고 합쳐줄 수 있으면 좋을 것이다. 하지만 한 가지 걸리는 것은, 두 컴포넌트가 하나의 빈 열만 두고 인접했을 때, 해당 열에 있는 메기를 두 컴포넌트에서 중복해서 세어줄 수 있다는 것이다. 이를 해결하기 위해 두 번째 관찰을 하자.

두 번째로, 두 컴포넌트 $[z, x - 1], [x + 1, y]$ 가 하나의 빈 열 $x$ 만을 두고 인접했을 경우, $x$에 인접한 부분인 $H[x - 1], H[x + 1]$ 이 $N$ 이라고 가정할 수 있다는 것이다. 이유는 다음과 같다.

• 만약에 $H[x - 2] \geq H[x - 1]$ 혹은 $H[x + 1] \le H[x + 2]$ 라고 하자. 일반성을 잃지 않고 $H[x - 1] \le H[x + 1]$ 이라 하면, $H[x - 1] = 0$ 으로 바꿨을 때 잡을 수 있는 메기의 수가 줄어들지 않는다. 고로 두 컴포넌트가 하나의 빈 열을 두고 인접하지 않다 가정할 수 있다.
• 고로 $H[x - 2] < H[x - 1], H[x + 1] > H[x + 2]$ 를 만족한다. 이 경우에는 $H[x - 1] = H[x + 1] = N$ 으로 바꿨을 때 잡을 수 있는 메기의 수가 줄어들지 않는다.

이러한 형태로 인접한 두 컴포넌트는 최댓값이 컴포넌트의 한 쪽 끝에 형성되어 있으니, 컴포넌트 자체가 최댓값 하나로만 이루어져 있거나, 아니면 최댓값을 기준으로 감소 / 증가 하는 형태를 띌 것이다. 두 컴포넌트 사이에 하나의 빈 열만 존재한다면 두 컴포넌트를 인접 하다고 하고, 인접한 컴포넌트들의 집합을 슈퍼컴포넌트 라고 하자. 슈퍼컴포넌트는 다음과 같은 구조를 이룬다:

• 가장 왼쪽에 있는 컴포넌트는 높이가 증가하며 오른쪽 끝의 높이가 $N$ 이다.
• 가장 오른쪽에 있는 컴포넌트는 높이가 감소하며 왼쪽 끝의 높이가 $N$ 이다. (왼쪽에 있는 컴포넌트랑 붙어 있을 수도 있다.)
• 그 사이에 있는 컴포넌트는 높이가 $N$ 이며 길이가 전부 $1$ 이다. (없을 수 있다.)

가장 왼쪽에 있는 컴포넌트가 열 $[L, M]$ 을 차지하고, 그 사이에 $M + 2, M + 4, \ldots, M + 2k$ 위치에 길이 1의 컴포넌트가 있고, 가장 오른쪽에 있는 컴포넌트가 열 $[M + 2k + 2, R]$ 을 차지한다고 하자. ($k \geq 0$) 이 때 우리가 잡게 되는 메기는

• 열 $[L - 1, M - 1]$ 구간에 있는, $(x, y)$ 좌표가 모두 단조증가하는 메기들의 체인
• 열 $M + 1, M + 3, \ldots, M + 2k + 1$ 에 있는 모든 메기들
• 열 $[M + 2k + 3, R + 1]$ 구간에 있는, $x$ 좌표가 단조증가하고 $y$ 좌표가 단조감소하는 메기들의 체인

(왼쪽 컴포넌트와 오른쪽 컴포넌트가 붙은 경우는 생략했다.)

이제 최적해의 형태를 충분히 제약시켰다. 위 최적해를 DP로 표현해 보자.

• $DP[i] = i$ 번 이하의 열을 슈퍼컴포넌트로 묶었을 때 메기 무게의 최대 합.
• $Down[p] = p$ 번 점을 감소 체인의 마지막 점으로 두었을 때 메기 무게의 최대 합.
• $Top[i] = i$ 번 열에 낚시터가 없을 때 메기 무게의 최대 합.
• $Up[p] = p$ 번 점을 증가 체인의 마지막 점으로 두었을 때 메기 무게의 최대 합.

다음과 같이 전이할 수 있다.

• $DP[i] = max(DP[i - 1], Top[i - 1], \max_{X[p] = i}Down[p])$
• $Down[p] = \max(Top[X[p] - 2], \\max_{X[q] \le X[p], Y[q] > Y[p]} Down[q]) + W[p]$
• $Top[i] = \max(Top[i - 2] + \sum_{X[p] = i} W[p], \\max_{X[p] = i} Up[p])$
• $Up[p] = \max(DP[X[p] - 1], \\max_{X[q] \le X[p], Y[q] < Y[p]} Up[q]) + W[p]$

이것을 단순하게 계산할 경우 $O((N + M)^2)$ 시간이 걸린다. 상태가 $N + M$ 개이고 전이 역시 다른 상태를 다 탐색하기 때문이다. 이 중 대다수 전이들은 보조 배열을 전처리하는 선에서 간단하게 최적화가 된다. $Down$ 과 $Up$ 에서 사용하는 전이는 단순하게 해결하기 어려운 편에 속하는데, $X[i]$ 를 증가시켜나가면서 처리할 경우, $Y[i]$ 좌표를 Key로 가지는 Max Segment Tree를 두면 이 역시 처리가 가능하다.

종합하면, 모든 상태 전이가 $O(\log N)$ 시간에 가능하여, 전체 문제가 $O((N + M) \log N)$ 에 해결된다.

문제 2. 죄수들의 도전

5점 풀이

5점 풀이는 문제를 이해했다면 어렵지 않다. 다음과 같이 프로토콜을 구성한다.

• 수 $0$ 이 쓰여졌다면, A번 가방을 열어서 동전 개수를 확인하고, 동전 개수를 적는다.
• $0$ 이 아닌 수가 쓰여있다면, 칠판에 적힌 수가 A번 가방에 있는 동전의 개수이다. B번 가방에 있는 동전 개수를 확인해 보면, 동전이 적게 든 가방을 고를 수 있다.

38점 풀이 ($m = 38$)

만약에 적힌 수가 $1, 2$ 중 하나라면, 위 풀이는 $3$ 개의 상태를 사용하여 두 수를 구분할 수 있다. 두 가방에 적힌 동전 개수를 이진 전개한 후, 위 풀이를 $\log N$ 번 반복하는 것으로, 상태 개수를 $O(N)$ 에서 $O(\log N)$ 개로 줄인다. 어떠한 수의 $k$ 번째 비트라는 것은, 해당 수를 $2^k$ 로 나눈 몫의 홀짝성을 뜻한다.

• 수 $0$ 이 쓰여졌다면, $A$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 만약 이 비트가 $0$ 이라면 칠판에 $1$을, $1$ 이라면 $2$를 쓴다.
• 수 $1, 2$ 가 쓰여졌다면, $B$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 이 비트가 $A$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, 칠판에 $3$ 을 써서 다음 절차로 넘어간다.
• 수 $3, 4, 5$ 에 대해서 $11$번째 비트로 위와 동일한 과정을 반복한다.
• ...
• 수 $36, 37, 38$ 에 대해서 $0$번째 비트로 위와 동일한 과정을 반복한다. 칠판에 $39$ 를 써야 할 이유는 없다.

최종적으로 $x \le 38$ 로 문제를 해결할 수 있다.

56점 풀이 ($m = 26$)

위 풀이에서는 $A$ 번 가방과 $B$ 번 가방의 역할에 명확한 비대칭성이 있다. $A$ 는 가방을 연 다음 그 정보를 다음 상태로 넘기고, $B$는 상태를 받은 후 판별만 하고 다시 $A$ 에게 턴을 넘긴다.

사실, $B$ 가 가방을 열 때 꼭 비트 하나만 보는 것은 아니다. $B$ 는 가방의 비트 수를 전부 볼 수 있다. 고로 대소를 확인한 이후, 무의미하게 $A$ 에게 턴을 넘겨줄 필요가 없고, 그 과정에서 더 낮은 비트를 확인하고 다음 상태로 넘기는 걸 같이 해 주면 된다. 이를 써보면 다음과 같다.

• 수 $0$ 이 쓰여졌다면, $A$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 만약 이 비트가 $0$ 이라면 칠판에 $1$을, $1$ 이라면 $2$를 쓴다.
• 수 $1, 2$ 가 쓰여졌다면, $B$ 번 가방을 열어서 $12$ 번째 비트를 확인한다. 이 비트가 $A$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, $B$ 의 $11$ 번째 비트가 $0, 1$ 인지에 따라 칠판에 $3, 4$ 을 써서 다음 절차로 넘어간다.
• 수 $3, 4$ 가 쓰여졌다면, $A$ 번 가방을 열어서 $11$ 번째 비트를 확인한다. 이 비트가 $B$의 그것과 다르다면 대소를 확인할 수 있다. 그렇지 않다면, $A$ 의 $10$ 번째 비트가 $0, 1$ 인지에 따라 칠판에 $5, 6$ 을 써서 다음 절차로 넘어간다.
• ...
• 수 $25, 26$ 에 대해서 $B$ 의 $0$번째 비트로 위와 동일한 과정을 반복한다. 칠판에 $27, 28$ 을 써야 할 이유는 없다.

65점 풀이 ($m = 24$)

꼭 이진 전개를 할 필요가 없다. $3$ 진수로 전개할 경우 $3^8 = 6561 \geq 5000$ 이라 모든 수를 판별할 수 있으며, 상태 수도 $3 \times 8$ 로 24개로 줄어든다. 이렇게 구현할 경우 9점을 더 받을 수 있다.

80점 풀이 ($m = 22$)

마지막 스텝에서 약간의 비효율성을 관찰할 수 있다. 위 풀이대로라면, 수 $19, 20, 21$ 이 쓰여졌을 때, 가방을 열어서 $B$의 $0$ 번째 비트를 확인하고 이에 따라서 다음 상태로 넘어갈 것이다. 하지만, $B$ 의 $0$ 번째 비트가 $0$일 경우 $B$ 는 무조건 $A$ 보다 작고, $2$ 일 경우 $B$ 는 무조건 $A$ 보다 크다. 두 수가 항상 다르기 때문이다. 고로, $B$ 의 $0$ 번째 비트가 $1$ 인 경우만 흥미로운 경우이다. 이 점을 관찰하면 두 개의 상태를 절약하여 15점을 더 받을 수 있다.

만점 풀이 ($m = 20$)

만점 풀이에서는, 위 $56$ 점 풀이를 줄이기 위해 사용한 두 가지의 작은 관찰들을 일반화해서, 위 관찰들로 Generate할 수 있는 모든 결정 방법 중 최적을 DP로 계산한다.

첫 번째 관찰은 이진 전개가 아니라 3진 전개를 해도 된다는 관찰이다. 더 나아가서, 전체 문제 자체가 일관된 전개를 할 필요는 없다. 첫 번째 단계에서는 $2$ 로 분할, 두 번째 단계에서는 $3$ 으로 분할, 세 번째 단계에서는 $4$ 로 분할... 하는 등 매번 사용할 수 있는 분할을 달리할 수 있다.

두 번째 관찰은 마지막 단계에서만 사용할 것 같아서 일반화가 힘들어 보이지만, 실제로는 그렇지 않다. 예를 들어서, 맨 처음에 $A$ 안에 들어 있는 동전의 수가 $1, N$ 중 하나라면, 더 이상 판단을 계속할 필요가 없다. $B$ 의 동전의 수가 다르기 때문에 바로 답을 판별할 수 있기 때문이다. 그렇지 않다면, 남은 동전의 수 후보는 $N - 2$ 개이다. 이들 중 구간을 $k$ 개로 나눈 후 $A$ 의 동전 수가 어떤 구간에 속하는지를 보내준다. $B$ 는 그 구간을 받은 후, 만약 내 동전 수가 해당 구간에 속하지 않으면 종료하고, 동전 수가 해당 구간의 양 끝점에 속하면 바로 판별하고, 아니면 분할을 계속 하면 된다.

첫 번째 관찰과 두 번째 관찰을 종합하면, 우리는 다음과 같은 수열 $k_1, k_2, \ldots, k_p$ 를 찾으면 된다:

• $\sum k_i$ 가 가능하면 작음
• $f_i(N) = \lceil (N - 2) / k_i \rceil$ 일 때, $f_p(f_{p - 1}(\ldots (f_1(N)))) = 1$

이러한 수열은 DP, 백트래킹 등 어떠한 방법으로든지 찾을 수 있다. $\sum k_i = 20$ 인 수열이 존재하며, 해당 수열로 위 전략을 구현하면 만점을 받을 수 있다. 가능한 수열 중 하나가 ${3, 3, 3, 3, 3, 3, 2}$ 라는 사실이 구현을 단순화하는 데 도움을 줄 수 있다. 여담으로 $\sum k_i \le 19$ 인 수열은 존재하지 않으니, 지금까지의 풀이 내용만 사용해서 더 좋은 풀이는 얻기 힘들 것이라 짐작이 된다.

문제 3. 송신탑

서브태스크 2 (11점)

어떠한 송신탑 부분집합이 답이 되기 위해서는 부분집합에 속하는 모든 탑 쌍이 서로 통신할 수 있어야 한다. 즉, 일종의 클리크를 이뤄야 하는데, 이렇게 생각하면 풀기 너무 어려우니, 조건을 더 단순화시켜보자.

송신탑 $x < y < z$ 에 대해서, $x, y$ 와 $y, z$ 가 통신할 수 있다면, $x, z$ 역시 통신이 가능함을 관찰할 수 있다.

• $x, y$ 가 통신할 수 있다는 것은, $[x + 1, y - 1]$ 구간에 $H[x] \le H[k] - D$ 인 $k$ 가 존재한다는 것이다.
• $y, z$ 가 존재한다는 것은, $[y + 1, z - 1]$ 구간에 $H[z] \le H[k] - D$ 인 $k$ 가 존재한다는 것이다.
• 고로, $x, z$ 에 대해서, $[x + 1, z - 1]$ 구간에서 저러한 $k$가 존재한다.

고로, 모든 탑 쌍이 서로 통신할 수 있다는 것은, 인접한 탑 쌍이 서로 통신할 수 있다는 것과 동치이다. 이제 DP로 문제를 해결할 수 있다. $DP[i]$ 를, $0, \ldots, i$ 번 점에 대해서, $i$ 번 송신탑을 포함하는 최적해의 최대 크기라고 정의하고, 통신 가능한 모든 $j < i$ 에 대해서 상태를 전이하면 된다. 통신 가능 여부는, $[j + 1, i - 1]$ 구간 최댓값을 관리하면 쉽게 계산할 수 있다. 답은 전체 $DP$ 배열의 최대이고, 시간 복잡도는 쿼리당 $O(N^2)$ 이다.

서브태스크 3 (23점)

두 송신탑 $i, j$ 가 통신하기 위해서는, 둘 사이에 송신탑 $k$ 가 존재하여, $H[i] + D \le H[k], H[j] + D \le H[k]$ 가 모두 만족된다는 뜻이다. $i, (k), j$ 와 같이, 중간에 이러한 송신탑을 끼워넣으면

• 인접한 원소간의 높이 차가 $D$ 이상이고
• 높이가 증가했다 감소한다

는 것을 관찰할 수 있다.

$i, j$ 가 송신탑일 때, 이렇게 $i, j$ 간의 송신을 도와주는 송신탑을 매개 송신탑 이라고 정의하자. 그리고, 송신탑의 최대 부분수열 $i_1, i_2, \ldots, i_k$ 를 구하는 대신, 매개 송신탑을 포함하는 최대 부분수열 $i_1, (j_1), i_2, (j_2), \ldots, i_{k-1}, (j_{k-1}), i_k$ 를 구하는 것으로 문제를 변형하자. 이렇게 할 경우, 최댓값에 대한 이야기를 할 필요 없이, 인접한 원소 간의 높이 차만 보면 되어서 편리하기 때문이다. DP를 다시 써 보자.

• $Up[i]$ 를, $i$ 번 송신탑을 매개 송신탑 으로 쓰는 부분 집합의 최대 크기
• $Down[i]$ 를, $i$ 번 송신탑을 쓰는 부분 집합의 최대 크기

라고 정의하면, $Up[i] = \max_{j < i, H[j] \le H[i] - D} Down[j], Down[i] = \max_{j < i, H[j] \ge H[i] + D} Up[j] + 1$ 와 같은 점화식이 성립한다. $H$ 를 좌표압축한 후, $Down, Up$ 배열을 좌표압축된 $H[i]$ 를 Key로 하는 Max Segment Tree로 관리할 경우 문제가 해결된다.

시간 복잡도는 쿼리당 $O(N \log N)$ 이다.

서브태스크 5 (40점)

서브태스크 3을 기준으로 이런 저런 관찰을 하다보면 서브태스크 5의 풀이가 얻어진다. 두 송신탑 $i, i + 1$ 에 대해서, $H[i] < H[i + 1]$ 이면 빨간 간선, $H[i] > H[i + 1]$ 이면 파란 간선으로 두 송신탑을 이어주자. 그렇다면 송신탑들은 길이 $N - 1$ 의 직선으로 연결될 것이며, 직선은 빨간 간선의 연속구간과 파란 간선의 연속구간으로 분할할 수 있을 것이다. 이제 여기서, (매개 송신탑을 포함하여) 송신탑의 부분집합을 고를 때, 다음과 같은 성질들이 성립한다.

• 같은 색으로 이루어진 간선 연속구간 안에서, 세 개 이상의 송신탑이 부분집합에 들어갈 수 없다. (높이가 증/감을 번갈아 해야 하기 때문에 정의상 자명)
• 같은 색으로 이루어진 간선 연속구간 안에서 골라야 하는 송신탑은, 연속구간의 양 끝점 뿐이다. (그렇지 않을 경우, 매개 송신탑은 값이 큰 쪽, 송신탑은 값이 작은 쪽으로 밀어넣으면 된다.)

이 관찰을 통해서, 중간에 있는 의미없는 원소를 제거해 주면서 송신탑의 높이가 증가/감소를 번갈아가게끔 할 수 있다. 하지만, 그렇다고 인접한 원소의 차이가 $D$ 이상임이 바로 보장되는 것이 아니라, 이것만으로는 바로 문제가 해결되지 않는다. 추가로 한 가지 관찰이 더 필요하다.

• 인접한 원소 간의 차가 가장 작은 송신탑 $(i, i + 1)$ 에 대해, 만약 $1 \le i \le N - 3$ 이고, 두 송신탑의 원소 차이가 $D$ 미만이라면, 두 송신탑을 모두 사용하지 않는 최적해가 존재한다.
  • 정의 상 두 송신탑을 모두 사용하는 해는 당연히 없다. 일반성을 잃지 않고 $H[i] < H[i + 1]$ 이며, $i$ 가 일반 송신탑이라고 하자. $i$ 가 일반 송신탑이기 때문에 $i + 2$ 는 현재 해에 포함되어 있지 않다. 또한 가정에 의해 $H[i] \geq H[i + 2]$ 이다. 고로 $i$ 를 $i + 2$ 로 대체시키면 된다.

고로, 이러한 경우에는 두 송신탑을 제거해 줄 수 있다. 이제 고정된 $D$ 에 대해서, 위와 같은 증/감이 번갈아 등장하는 송신탑을 std::set과 같은 자료구조에, 인접한 송신탑의 높이 차와 위치를 Heap과 같은 자료구조에 관리하자. 모든 송신탑의 원소 차이가 $D$ 이상이 될 때까지, 위와 같이 송신탑들을 적절히 지워준 후, 최후에 std::set의 크기를 통해서 송신탑 부분 집합의 크기를 계산하면 된다. 양 끝점 처리는 위 관찰로 바로 되지 않으니 적절히 처리해 줘야 한다.

이제 서로 다른 $D$ 값에 대해서도 문제를 해결해야 하는데, 사실 위 풀이는 모든 $D$ 에 대해서 최적 송신탑 집합을 관리함을 관찰할 수 있다. 수열의 길이가 $1$ 이 될 때까지 인접한 송신탑을 지워준 후, 매 연산 이후 집합의 크기를 기록해 두자. 쿼리로 $D$ 가 주어지면, $D$ 미만의 원소 차이를 모두 지운 직후 집합의 크기를 반환하면 된다.

시간 복잡도는 $O((N + Q) \log N)$ 이다.

만점 풀이

구간이 $[0, N - 1]$ 이 아니더라도 풀이 자체가 큰 차이가 나지는 않는다. 구간에서 현재 제거하지 않은 송신탑의 개수에, 구간의 양 끝점 처리만 적절히 더해주면 되기 때문이다.

현재 제거하지 않은 송신탑의 개수는, $D$ 혹은 그 이후에 지워진 송신탑의 개수와 동일하다. 40점 풀이에서 (매개 송신탑 아닌) 송신탑을 제거할 때, 송신탑이 지워진 시점과 그 위치를 기록해 둔다. 각각의 쿼리가 들어올 때, $D$ 이후에 지워진 송신탑 중 구간 $[L, R]$ 에 있는 송신탑의 개수를 센다. 이는 Persistent Segment Tree로 해결할 수 있다.

양 끝점 처리를 하기 위해서는, 현재 제거하지 않은 송신탑 중 가장 왼쪽 / 오른쪽에 있는 송신탑을 알아야 한다. 위에서 사용한 Persistent Segment Tree를 동일하게 사용하면 된다. 이후 이 왼쪽과 오른쪽에 추가로 송신탑이 더 올 수 있는지는, 구간 최대 / 최솟값을 빠르게 구할 수 있으면 해결 가능하다.

시간 복잡도는 $O((N + Q) \log N)$ 이다.

문제 풀이 한 줄 요약

• fish: 문제 구조에 대한 관찰을 통해서 최적해의 구조를 제약시키고, 제약된 구조 안에서 DP를 사용하여 해결한 후 자료구조를 사용하여 계산을 고속화
• prison: $2 \log N$ 개의 쿼리를 사용하는 전략을 구상 후 몇 가지 국소적 최적화를 고안. 이러한 국소적 최적화로 얻을 수 있는 이론상 쿼리 최소치를 찾은 후 이에 따라 구현.
• towers: 최적해가 배열의 극소/극대점 만 사용한다는 점을 관찰한 후, 답에 포함되지 않는 극소/극대점을 반복적으로 지우는 식의 알고리즘 고안. 이후 해당 알고리즘이 사실 모든 D, 모든 구간 쿼리에 대한 답을 구함을 관찰하고 그에 맞게 자료 구조 등을 사용하여 수정