IOI 2025 Day 2

볼리비아 수크레에서 IOI 2025 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.

• 우민규, 100 / 99.33 / 93 / 100 / 82.45 / 100, 574.78점, 2등 (금메달)
• 이유찬, 100 / 58.89 / 86 / 66 / 72.89 / 83, 466.77점, 16등 (금메달)
• 정민찬, 100 / 79.77 / 100 / 66 / 30 / 83, 458.77점, 19등 (금메달)
• 변재우, 39 / 76.25 / 86 / 100 / 64.45 / 83, 448.7점, 24등 (금메달)

한국 팀은 Day 2에도 기세를 이어 대단히 좋은 성적을 내었다. 우민규 학생은 Day 1에도 4등의 성적으로 대회를 마무리했는데, Day 2에서는 이를 더 끌어올려 종합 2등의 아주 우수한 개인 성적으로 대회를 마무리했다. Day 1 금메달권이었던 이유찬 학생과 정민찬 학생 역시 Day 2에서도 좋은 결과를 유지하였다. Day 1 60등이었던 변재우 학생은 Day 2 종합 11등의 성적으로 점수를 크게 올려 금메달권에 진입하였다. 이에 따라 한국 팀은 1992년 이후 IOI 출전 이래 첫 전원 금메달 업적을 달성하였다. 축하합니다! 정민찬 학생과 변재우 학생의 경우 내년에도 IOI를 참가할 수 있다. 앞으로도 좋은 결과를 내기를 기원한다.

올해 IOI의 우승자는 중국의 Hengxi Liu 학생이다. Day 1을 만점, Day 2를 종합 1등의 성적으로 마무리하였고, 총 591.23점의 총점으로 대회를 마쳤다. 축하합니다! 올해 참가 팀 중 전원 금메달을 달성한 팀은, 중국 / 한국 / 루마니아 총 3개국이다. 총점 합으로는 중국이 가장 높으며, 한국의 총점이 루마니아보다 아주 약간 (1949.02 > 1938.13) 높다.

올해 Day 2의 마지막 문제인 장애물(obstacle) 은 한국의 조승현(ainta) 가 출제하였다. 조승현은 IOI 2020에서도 plants라는 문제를 출제했으며, 한국 IOI 선발고사를 포함한 다양한 대회에서 꾸준히 출제 활동을 이어나가고 있다. 한국 출제자들이 좋은 문제를 IOI에 기여하는 것이 바람직하고 좋다고 생각한다. 축하합니다!

마지막으로, 관심이 있다면 올해 IOI를 참가한 이유찬 학생의 참가 후기 와, 현장 코치로 참여한 박상훈 코치의 문제 풀이 를 읽어보는 것을 추천한다. Day 2의 이주(migration) 문제 풀이는 박상훈 코치의 풀이를 읽고 작성하였다.

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

Day 2 Problems PDF

festival-en.pdf

0.14MB

festival-ko_KR.pdf

0.23MB

migrations-en.pdf

0.21MB

migrations-ko_KR.pdf

0.46MB

obstacles-en.pdf

0.16MB

obstacles-ko_KR.pdf

0.23MB

Problem 4. 축제 (festival)

쿠폰 -> 물건, 토큰 -> 동전으로 표현한다. (쿠폰으로 토큰을 산다는 말을 벌써 10번 넘게 쓰다 지웠다.)

서브태스크 1 (5점)

$T[i] = 1$ 이니, 물건을 구매하면 그냥 가격만큼 동전 개수가 줄어든다. 물건 가격의 합을 $A$ 이하로 하면서 최대한 많은 물건을 구매하면 된다. 모든 물건을 가격 순으로 정렬한 후, 가장 저렴한 물건부터 사면 된다.

서브태스크 2, 4 (27점)

같은 $T[i]$ 를 가진 물건이 여럿 있으면, 이 중 가격 $P[i]$ 를 최소로 하는 물건을 구매하지 않을 이유가 없다. 각 $t = 1, 2, 3, 4$ 에 대해서, $T[i] = t$ 인 물건들을 $P[i]$ 순으로 정렬하자. 매 순간 구매한 물건의 집합은 $P[i]$ 순서상 prefix를 이룬다. 즉, 현재 $T[i] = t$ 인 물건을 몇 개 구매했는지 알면 무슨 물건을 샀는지도 바로 알 수 있다. $DP[c_1][c_2][c_3][c_4]$ 를, $T[i] = t$ 인 물건을 $c_t$ 개 샀을 때 동전 개수의 최댓값이라고 정의하자. 서브태스크 $4$ 에서는 이 DP를 $O(N^4)$ 에 계산할 수 있고, 서브태스크 2에서는 이 DP를 $O(N^2)$ 에 계산할 수 있다 ($c_3 = c_4 = 0$).

한가지 까다로운 점은 $DP$ 값이 매우 커질 수 있다는 점인데, 동전의 개수가 $N\cdot A$ 이상이면 남은 물건을 전부 구매할 수 있다. 고로, DP 값이 $10^{15}$ 초과로 넘어가면 $10^{15}$ 로 잘라줘도 문제가 없다.

서브태스크 3 (39점)

$T[i] = 1$ 인 물건을 산 직후 $T[j] > 1$ 인 물건을 샀다고 하자. 두 물건을 다 살 수 있었으니 어차피 동전은 $P[i] + P[j]$ 이상으로 있었을 것이다. 그런데 $T[j] > 1$ 인 물건을 사고 $T[i] = 1$ 인 물건을 사면, 남은 동전의 개수에 비례해서 추가 보상을 얻고 $T[i] = 1$ 인 물건을 살 수 있다. 고로, 이 경우 $T[i] = 1$ 인 물건을 나중에 사는 것이 무조건 이득이다.

Exchange argument로 위와 같은 논리를 반복하면, $T[i] > 1$ 인 물건을 다 산 이후에 $T[i] = 1$ 인 물건을 사는게 이득임을 알 수 있다. $T[i] = 2$ 인 물건을 몇개 샀는지 고정하자. 어차피 가격이 낮은 것부터 샀을 테니, 산 이후 남은 동전 개수를 알 수 있다. 남은 동전 개수를 알면, 이를 통해 $T[i] = 1$ 인 동전을 몇개 더 살 수 있는지도 부분합과 이분 탐색을 통해서 알 수 있다. 고로, 모든 경우의 수를 $O(N \log N)$ 에 계산할 수 있어 문제가 해결된다.

서브태스크 5 (66점)

서브태스크 5에서는 모든 물건을 살 수 있다는 것이 보장되기 때문에, 물건을 사는 정확한 순서만 찾을 수 있으면 문제를 해결할 수 있다. 동전의 개수가 중간에 음수가 되어도 되고, 물건을 모두 산 이후 남은 동전의 개수를 최대화하는 유형의 문제 가 여럿 있다. 이러한 문제의 전략을 사용할 수 있을까? 모든 물건을 살 수 있다면 남은 동전의 개수가 $0$ 개 이상이어야 하며, 중간에 동전의 개수가 음수가 될 수는 없다.

다행이도, 남은 동전의 개수가 $0$ 개 이상이 되는 순서만 있으면, 중간에 동전의 개수가 음수가 되는 경우를 걱정할 필요는 없다. 만약 어떤 순간에 동전의 개수가 음수가 된다면, 이후 동전의 개수를 절대 $0$ 이상으로 되돌릴 수는 없다. 고로, 남은 동전의 개수가 $0$ 개 이상이 되기만 하면 항상 올바른 순서이다.

이제 남은 동전의 개수를 최대화하는 문제를 풀어보자. 초기 동전 개수가 $X$ 이고, 두 물건 $(P_1, T_1), (P_2, T_2)$ 가 있다고 하자. 둘을 사는 순서는 두 가지이다:

• $(P_1, T_1)$ 인 물건을 사고 $(P_2, T_2)$ 인 물건을 사는 시나리오에서는, 동전 개수가 $X \rightarrow T_1 (X - P_1) \rightarrow T_2 (T_1 (X - P_1) - P_2)$ 가 된다.
• $(P_2, T_2)$ 인 물건을 사고 $(P_1, T_1)$ 인 물건을 사는 시나리오에서는, 동전 개수가 $X \rightarrow T_2 (X - P_2) \rightarrow T_1 (T_2 (X - P_2) - P_1)$ 가 된다.

$(P_1, T_1)$ 을 $(P_2, T_2)$ 보다 먼저 사는 것을 정당화하려면, $T_2 (T_1 (X - P_1) - P_2) \geq T_1 (T_2 (X - P_2) - P_1)$ 가 성립해야 한다. 이 식을 정리하면:

$T_1 T_2 P_2 + T_1 P_1 \geq T_1 T_2 P_1 + T_2 P_2$
$P_2 + P_1 / T_2 \geq P_1 + P_2 / T_1$
$P_2 (1 - 1/T_1) \geq P_1 (1 - 1/T_2)$
$\frac{P_1}{1 - 1/T_1} \leq \frac{P_2}{1 - 1/T_2}$

이 된다. 즉, Exchange argument에 의해서 남은 동전 개수를 최대화하는 순서는 모든 값을 $P / (1 - 1/T)$ 순으로 정렬해서 얻을 수 있다. $T = 1$ 인 경우에는 저 값을 계산할 수가 없는데, 서브태스크 3의 논리에 의해서 $T = 1$ 인 경우는 항상 $T > 1$ 인 경우보다 뒤에 오게 된다. 고로 $T = 1$ 의 우선순위가 가장 뒤로 밀리게끔 정렬해 주면 된다.

모든 물건을 이러한 순서로 정렬하면 $O(N \log N)$ 시간에 서브태스크 5를 해결할 수 있다.

서브태스크 6 (82점)

모든 물건에 대해서 $T[i] (A - P[i]) < A$ 가 성립한다. 즉, 초기 상태에서 해당 물건을 구매하면 무조건 손해가 발생한다. 더 나아가서, 그 이후의 동전 개수가 $X \leq A$ 개라면, $T[i] (X - P[i]) < X$ 역시 성립하기 때문에, 현재 가격과 상관 없이 가지고 있던 동전을 잃게 된다.

초기 금액이 $A$ 였다고 할 때, $A$ 에서의 손실이 각 물건을 사면서 얼마나 증가하는지를 살펴보자. $L \geq 0$ 에 대해, $A - L$ 인 상태에서 물건 $i$ 를 사서 동전 개수가 $A - L^\prime$ 이 되었다면, $A - L^\prime = (A - L - P[i]) T[i]$ 가 성립한다. 문제 조건과 결합해서 전개하면

$A - L^\prime = (A - L - P[i]) T[i] < A - L \cdot T[i]$
$L^\prime > L \cdot T[i]$

고로, 초기 금액에서의 손실이 매번 최소 $T[i]$ 배 증가한다. 손실액은 $A$ 이상일 수 없기 때문에, 이는 $T[i] \geq 2$ 인 물건을 최대 $\log_2 A + O(1)$ 개만 구매할 수 있음을 의미한다. 여기서 서브태스크 3/4의 풀이로 환원할 수 있지만, 서브태스크 5의 관찰을 사용해서 조금 더 빠르고 구현하기 쉬운 풀이를 소개한다. 모든 $T[i] \geq 2$ 인 물건을 서브태스크 5의 순서대로 정렬하자. 물건을 모두 구매하지 않고 그 부분집합만 구매한다고 하더라도, 물건을 구매하는 순서는 서브태스크 5의 순서와 동일할 것이다. 고로 이 순서에 기반해서 DP를 구성할 수 있다. $DP[i][j]$ 를 첫 $i$ 개의 물건 중 $j$ 개의 물건을 샀을 때 동전 개수의 최댓값이라고 정의하자. 살 수 있는 물건의 수가 $\log_2 A + O(1)$ 개이니 이 DP를 $O(N \log A)$ 시간에 계산할 수 있다 (반환값이 $10^{15}$ 초과일때 오버플로우를 막기 위해 적당히 잘라주는 것을 잊지 말자.)

DP를 전부 계산한 이후에는, $T[i] \geq 2$ 인 물건을 $p$ 개 구매했을 때 남은 동전 개수를 알 수 있다. 모든 $p$ 에 대해서, 남은 동전 개수로 $T[i] = 1$ 인 물건을 가격 순으로 구매해보면, 살 수 있는 물건 수의 최댓값을 알 수 있다. DP 테이블을 역추적하면 최적해 역시 반환 가능하다.

만점 풀이

서브태스크 5와 6의 풀이를 합치면 만점 풀이가 나온다. 서브태스크 6이 전체 문제에 대해 강력한 힌트를 준다고 느껴진다.

서브태스크 5의 순서대로 모든 물건을 정렬하자. 앞에서 설명했듯이, 모든 물건을 구매하지 않는다고 하더라도 서브태스크 5의 순서를 따라도 된다. 현재 동전의 개수를 $C = A$ 라고 했을 때, 만약 첫 번째 물건이 $T[i] (C - P[i]) \geq C$ 를 만족할 경우, 이 물건을 사지 않을 이유가 없다: 물건의 개수를 늘릴 뿐만 아니라 동전의 개수 역시 손해를 보지 않기 때문이다. 동전의 개수가 줄지 않는다면, 계속해서 맨 앞에 있는 물건을 구매하자. 이 과정에서 $C \geq NA$ 가 되었을 경우 모든 물건을 살 수 있으니 그냥 현재 순서를 반환하면 된다.

만약에 첫 번째 물건이 $T[i] (C - P[i]) < C$ 를 만족한다고 하자. 이 경우, 남은 모든 물건이 $T[i] (C - P[i]) < C$ 를 만족함을 증명할 수 있다. 만약 $T[j] (C - P[j]) \geq C$ 를 만족하는 물건이 있다고 하자.

$T[i] (C - P[i]) < C \leq T[j] (C - P[j])$
$(T[i] - 1) C < T[i] P[i]$
$T[j] P[j] \leq (T[j] - 1) C$
$\frac{T[j]P[j]}{T[j] - 1} \leq C < \frac{T[i]P[i]}{T[i] - 1}$

이는 서브태스크 5와 같이 모든 물건이 정렬되어 있다는 가정에 모순이다. (0으로 나누는 문제가 있지만, $T[i] = 1$ 인 물건들은 어차피 $T[i] (C - P[i]) < C$ 이다.) 고로, 서브태스크 6의 풀이를 그대로 적용하여 전체 문제를 $O(N \log (NA))$ 시간에 해결할 수 있다.

Problem 5. 이주 (migration)

서브태스크 1, $Z \le 9999$ (10점)

$dist(u, v)$ 를 두 정점 $u, v$ 간의 거리라고 정의하자. $0$ 을 보내다가 마지막 메시지에 $dist(0, i)$ 를 최대화하는 $i$ 를 적어 보내면 된다.

서브태스크 1, $Z \le 3$ (30점)

$i \le N - 14$ 까지 $0$ 을 보낸다. 이후 남은 14개의 메시지를 사용하여 정답을 커뮤니케이션한다. 14개의 메시지를 보내기 전 $dist(0, i)$ 를 최대화하는 $1 \le i \le N - 14$ 을 계산하고, 이를 길이 14의 이진 문자열 $s_1, s_2, \ldots, s_{14}$ 로 변환한다. 남은 14개의 메시지로:

• 이진 문자열의 한 비트 $s_i$
• 이번에 들어온 정점이 $dist(0, i)$ 의 최댓값을 갱신했다면 $1$, 아니면 $0$
  을 보내자. $[0, 3]$ 범위의 메시지만으로도 2비트를 충분히 보낼 수 있다.

두 번째 실행에서는:

• 만약에 $dist(0, i)$ 가 갱신된 메시지가 14개 중 존재한다면 그 중 가장 마지막 메시지에 대응되는 정점
• 없다면 이진 전개된 $i$

를 반환하면 된다.

서브태스크 2부터는 모든 풀이에서 $Z = 4$ 를 가정한다.

$M \le 19$ (81.28점)

서브태스크 1과 유사하게 진행하는데, 이번에는 양 끝점을 전부 보내야 해서 $[0, 4]$ 안에 값을 모두 넣기가 조금 빡빡하다. $M = O(\log N)$ 을 달성할 수 있는 방법이 여러 가지 있는데 그 중 가장 구현하기 간단한 방법을 소개한다.

$i < N - 19$ 까지는 $0$ 을 보낸다. 이제 $i = N - 19$ 가 되었을 때, 마지막 $18$ 개 정점을 제외한 트리의 지름을 $O(N)$ 시간에 계산할 수 있다. 계산한 끝점을 $u, v$ 라고 하였을 때:

• $i \in [N - 19, N -14]$ 에서 6번의 메시지로 $u$ 를 보낸다. $(u \le N - 19 \le 5^6$)
• $i \in [N - 13, N - 8]$ 에서 6번의 메시지로 $v$ 를 보낸다. ($v \le N - 19 \le 5^6$)
• $i \in [N - 7, N - 6]$ 에서 바뀐 $u$ 의 위치를 보낸다 ($13 \le 5^2$)
  • 새로운 $u$ 의 위치는 $[N - 18, N - 7]$ 중 하나이다. 만약 지난 $u$ 의 위치가 그대로 유지되었다면 $24$ 를, 아니면 $N - 7 - u$ 를 보내면 된다.
• $i \in [N - 5, N - 4]$ 에서 바뀐 $v$ 의 위치를 보낸다 ($8 \le 5^2$)
  • 새로운 $v$ 의 위치는 $[N - 12, N - 5]$ 중 하나이다. 만약 지난 $v$ 의 위치가 그대로 유지되었다면 $24$ 를, 아니면 $N - 5 - v$ 를 보내면 된다.
• $i = N - 3$ 에서 바뀐 $u$ 의 위치를 보낸다.
  • 새로운 $u$ 의 위치는 $[N - 6, N - 3]$ 중 하나이다.
• $i = N -2$ 에서 바뀐 $v$ 의 위치를 보낸다 ($8 \le 5^2$)
  • 새로운 $v$ 의 위치는 $[N - 4, N - 2]$ 중 하나이다.
• $i = N - 1$ 에서 바뀐 $u, v$ 의 위치를 모두 보낸다.
  • 새로운 $u$ 의 위치는 $[N - 2, N - 1]$ 중 하나이고, 새로운 $v$ 의 위치는 $N - 1$ 이다. 고로 $2 \times 3 = 6$ 가지 경우가 있는데, 지름일 경우 $u = v = N - 1$ 이 성립할 수는 없기 때문에, 이 경우를 무시하면 $5$ 가지 경우가 되어서 위치를 보낼 수 있다.

$i$ 번 정점이 추가된 상태에서 새로운 지름을 계산할 때, 기존 지름의 끝점을 둘 다 바꾸지 않도록 해야 함에 유의하자. 기존 지름이 $(u, v)$ 라면, 새 지름은 $(u, v), (u, i), (i, v)$ 중 하나에 속한다.

위 알고리즘을 내가 구현했을 때는 $M \le 17$ 이 나와서 83점 정도를 얻었고, $M \le 11$ 을 얻어서 93점 정도를 얻은 사람도 있는 것 같다. 결국 메시지 개수가 실제 상한만큼 보내지려면 내가 보내는 모든 메시지가 $0$ 초과이도록 테스트 케이스를 잘 설계해야 하는데, 준비하는 입장에서 쉽지 않을 것 같다.

만점 풀이

만점을 받기 위해서는 $M \le 8$ 까지 줄여야 한다. 어렵기보다는 굉장히 더러운 종류의 문제에 가깝다. 작년 message와 다르게 올해 소수점 문제들은 별로 흥미롭지 않다고 느껴지는데, 다행이도 두 문제 다 변별력이 거의 없었다.

난 이 문제의 만점 풀이를 고민해 보지 않았다. 아래 적게 될 풀이는 모두 박상훈 코치의 블로그 의 내용을 표절했다 기반으로 작성되었다.

81점 풀이의 한계점은 모든 통신을 마지막 $M$ 개의 메시지를 사용해서 한다는 점이다. 가능한 지름의 경우의 수가 $5^{11}$ 을 초과하기 때문에, 이 전략은 최소 $12$ 개의 메시지를 강제한다. 실제로 메시지를 보낼 수 있는 시간이 $N$ 개라는 점을 사용하면, 언제 메시지를 보냈는지를 사용하여 더 많은 정보를 통신할 수 있다. 예를 들어서, 보내는 사람이 답을 처음부터 알고 있다면, 단순히 지름의 양 끝점 $u, v$ 에 메시지 $1$ 을 실어서 $M = 2$ 로 문제를 해결할 수 있다. 물론 처음부터 답을 아는 것은 당연히 불가능하지만, $12$ 번의 꽉 찬 메시지를 보내는 대신 긴 기간에 걸쳐서 적은 개수의 메시지를 보내는 것의 효율성을 보여주는 예시이다.

만점 풀이에서는 필요한 정보들을 단계적으로 나눠서 보낼 것이다. 첫 단계가 시작하기 전, 현재까지 추가된 모든 끝점이 지름의 후보가 될 수 있다. $i$ 번 단계가 시작되었고 그 길이가 $A$ 라면, 그동안 한 번의 메시지는 총 $4A + 1$ 의 정보를 보낼 수 있다. 이 정보를 통해서, 어떠한 끝점들을 후보에서 쳐낼 수 있다. DP 등을 사용하여, 다음과 같은 $5$ 개의 단계를 찾아낼 수 있다:

• $116$의 시간 동안 $465$의 정보를 보내면, 끝점의 후보를 $334$ 개로 줄일 수 있다 ($465 = 30 \times 31 / 2$).
• $20$의 시간 동안 $81$의 정보를 보내면, 끝점의 후보를 $\lceil (116+334) / 9 \rceil = 50$ 개로 줄일 수 있다.
• $6$의 시간 동안 $25$의 정보를 보내면, 끝점의 후보를 $\lceil (50 + 20) / 5 \rceil = 14$ 개로 줄일 수 있다.
• $2$의 시간 동안 $9$의 정보를 보내면, 끝점의 후보를 $\lceil (14+6) / 3 \rceil = 7$ 개로 줄일 수 있다.
• $2$의 시간 동안 $9$의 정보를 보내면, 끝점의 후보를 $\lceil (7+2) / 3 \rceil = 3$ 개로 줄일 수 있다.

최종적으로 끝점의 후보가 $3$ 개 있고, 시간이 $2$만큼 지난 상태에 도달한다 (즉 5단계의 마지막 시간에 지름이 업데이트 되어 있을 수 있다.) $3$ 의 시간 동안 메시지 $3$개를 써서 지름을 결정할 수 있으면 $M \le 8$ 로 문제를 해결할 수 있다. 이를 어떻게 하는지 소개한다. 기존 지름의 끝점 후보를 $0, 1, 2$ 라고 하고, $N - 4, N - 3, N - 2, N - 1$ 번 정점을 $A, B, C, D$ 라고 하자. (왼쪽 $0$ 과 오른쪽 $0$ 은 다른 정점임에 유의하면 좋다.)

$N - 3$ 번 정점에서는 $A, B$ 에 대한 정보를 안다. 다음과 같이 $5$ 개의 그룹으로 상태를 나누고, 그룹 번호를 반환하자.

• $(00, 01, 10, 11, 0A)$
• $(22, 20, 2A, A2, A0)$
• $(02, 0B, 12, 1A)$
• $(21, 1B, 2B, AB)$
• $(A1, B0, B1, B2)$

$N - 2$ 번 정점에서는 $A, B, C$ 에 대한 정보를 안다. 이전에 나눈 $5$ 개의 그룹 각각에 대해, 다음과 같이 $5$ 개의 그룹으로 또 상태를 나누자 ($i$ 번째 줄은 $N - 3$ 번 정점에서 $i$ 번째 그룹에 속한 지름 후보들에 대해 나누는 그룹을 나타낸다).

• $((00, 01), (10, 11), (0C, 1C), (C0, C1), (0A, CA))$
• $((22, 20), (2A, 2C), (A2, AC), (C0, A0), (C2, CA))$
• $((02, 0B), (0C, 1C), (12, 1A), (C2, CA), (CB))$
• $((21, 2C), (1B, 2B), (AB, CB), (1C, AC), (C1))$
• $((A1, AC), (B0, B1), (B2, BC), (C0, C1), (C2))$

최종적으로, 가능한 지름 후보가 $2$ 개로 좁혀졌으며, 하나의 끝점의 값은 정확히 알게 된다 (즉, 후보가 $xy, xz$ 꼴이거나 $yx, zx$ 꼴). 일반성을 잃지 않고 후보가 $xy, xz$ 꼴이라고 하자. $N -1$ 번 정점에서는 가능한 지름 후보가 $\{xy, xz, xD, Dy, Dz\}$ 꼴로 나온다. 이 중 무엇인지를 반환하면 전체 문제를 해결할 수 있다. (마지막 몇 문단은 정말 그대로 베껴 써서 미안하지만, 아쉽게도 내가 더할만한 내용이 없다.)

Problem 6. 장애물 (obstacles)

서브태스크 1, 3 (23점)

$NM \leq 600,000$ 이 성립한다. DFS / Union Find 등으로 연결 컴포넌트를 구하고 쿼리로 주어진 두 셀이 같은 컴포넌트에 있는지 확인하면 된다.

서브태스크 2 (37점)

마지막 줄이 아닌 곳에서 좌우로 이동할 이유가 없다. $(0, S), (0, D)$ 가 건조하면 $(N-1, S), (N-1, D)$ 도 건조하니, $T[0] = T[N - 1]$ 으로 두고 $N =1$ 인 경우로 환원할 수 있다.

서브태스크 5 (83점)

서브태스크 5의 경우 모든 쿼리가 $L = 0, R = M - 1$ 을 만족한다. 사실 이 문제에서 의미가 있는 몇 안되는 서브태스크이다. 만점 풀이가 이상한 것도 아니고, 83점과 100점 사이에 $O(NM)$ 서브태스크 같은 게 있을 법도 한데 왜 없는지 모르겠다. Day 2 모든 문제에 대해서 부분점수가 대단히 관대하게 매겨져 있다고 느꼈다.

서술 편의상 모든 $H[i]$ 가 다르다고 가정한다. $(H[i], i)$ 쌍을 사전순으로 비교하는 식으로 하면 구현에 큰 차이가 없다.

문제의 각 셀을 $NM$ 개의 정보를 사용하지 않고 표현하는 방법을 고민해 보자. 현재 있는 건조한 셀에서 행을 바꾸지 않고 움직일 수 있는 열들의 연속 구간을 생각해 보자. 이 연속 구간은 구간에 있는 셀의 최댓값 에 따라 정의된다. 이 최댓값보다 값이 작은 셀들은 모두 도달 가능하고, 큰 셀들은 모두 도달이 불가능하다. 다시 말해, $L[i]$ 를, $j < i, H[j] > H[i]$ 인 최대 $j$ (없으면 $-1$), $R[i]$ 를 $j > i, H[j] > H[i]$ 인 최소 $j$ (없으면 $M$) 이라고 정의하면, 도달 가능한 $H$ 의 최댓값이 열 $i$ 에서 얻어진다면, $[L[i] + 1, R[i] - 1]$ 번 열을 모두 도달 가능하다.

$0$ 번 행에서 바로 $S \rightarrow D$ 로 갈 게 아니면, 이 연속 구간을 넓히면서 $D$ 에 도달할 수 있도록 최대한 노력해야 할 것이다. 이를 조금 더 구체적으로 정의하기 위해 몇 가지 관찰이 필요하다.

관찰 1. 현재 $[L[i] + 1, R[i] - 1]$ 번 열을 도달 가능하고, 구간을 넓히기 위해 $L[i]$ 번 열을 도달하고 싶다고 하자. 이를 위해서는, 현재 도달 가능한 열 중 $H[j]$ 값을 최소로 하는 열을 타고 간 후, $L[i]$ 번 열을 도달할 수 있을 정도로 $T[k]$ 값이 큰 행 $k$ 를 찾으면 된다. 이후 이 행에서 $L[i]$ 번 열로 이동하면 구간을 넓힐 수 있다.

관찰 2. 도달 가능한 열의 집합이 같은 행이라면, 번호가 큰 행을 선택할 이유가 없다. 고로 같은 행들 중 번호가 가장 낮은 행에 있다고 가정해도 되고, 이에 따라 실제로 저 열의 구간이 상태에 정확히 대응하게 된다.

관찰 3. $[L[i] + 1, R[i] - 1]$ 형태의 구간은 트리를 이룬다. 구체적으로, $H$ 의 최댓값을 루트로 하는 Cartesian Tree의 서브트리 구간이 정확히 저것에 일치한다.

관찰 4. $[L[i] + 1, R[i] - 1]$ 에서 구간을 넓히기 위해서는, $L[i]$ 번 열에 도달하거나 $R[i]$ 번 열에 도달할 수 있어야 한다. 일반성을 잃지 않고 $H[L[i]] < H[R[i]]$ 라고 하자. $R[i]$ 번 열에 도달할 수 있는데 $L[i]$ 번 열에 도달할 수 없는 경우는 없다. 고로, $L[i], R[i]$ 중 높이가 높은 쪽의 확장은 지금 당장 시도할 필요가 없고, 높이가 낮은 방향으로 확장을 시도하면 된다.

관찰을 종합하면 다음과 같다. 서술 편의상 Cartesian Tree가 무엇인지 안다고 가정한다.

• 각 상태는 Cartesian Tree의 노드에 정확히 대응된다.
• 각 상태에서 도달 가능한 열의 집합은, Cartesian Tree 상 특정 노드의 서브트리에 속하는 열의 집합이다.
• 구간을 넓히는 것은 Cartesian Tree의 특정 노드에서 부모 노드로 이동하는 것이다.

셀 $(0, S)$ 에서 $(0, D)$ 로 가는 것은, 노드 $S$ 와 노드 $D$ 에서 구간 넓히기를 반복해서 같은 노드에 도달할 수 있는가와 동일하다. 각 노드 $v$ 에 대해서, Cartesian Tree 상 부모 $par_v$ 로 상태를 이동 가능한지 여부를 전부 계산해두자. 서로 이동 가능한 간선들으로 그래프를 만들었을 때, $(0, S)$ 에서 $(0, D)$ 를 갈 수 있다는 것은 $S$ 와 $D$ 가 같은 컴포넌트에 속한다는 것과 동치이다. 고로, 저 여부만 전부 계산해 두면 전체 문제를 Union-Find로 해결할 수 있다.

$f(t)$ 를, $0$ 번 행에서 높이 $t$ 초과의 행에 도달할 수 있는 최대 $h$ 라고 정의하자. $T$ 의 Prefix minimum과 Prefix maximum을 계산해 두면, 높이가 $t$ 초과인 가장 가까운 행을 이분 탐색으로 찾을 수 있고, 그 행까지 가는 길 상 $T[i]$ 의 최솟값 역시 알 수 있다. 이 최솟값보다 $H[j]$ 가 작은 열이 서브트리 안에 있으면, 높이 $t$ 초과의 행에 도달할 수 있다. 즉, $submin_v$ 를 $v$ 의 서브트리에 있는 열 중 $H[j]$ 의 최소라고 정의하면 (트리 DP로 계산 가능), $submin_v < f(H[par_v])$ 일 때 $v$ 에서 $par(v)$ 로 이동이 가능하다. 각 $v$ 마다 이를 $O(\log N)$ 시간에 판정할 수 있으니, 전체 문제를 $O(N + M \log N)$ 시간에 해결할 수 있다.

만점 풀이