IOI 2024 Day 2

(9/15 06:58 - Hieroglyphs 만점 풀이를 추가했다.)

(9/13 09:44 - 초판 작성)

이집트 알렉산드리아에서 IOI 2024 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.

• 김은성, 100 / 58.64 / 59 / 3 / 78 / 64.0, 362.64점, 29등 (금메달)
• 우민규, 100 / 31.40 / 59 / 3 / 100 / 64.0, 357.40점, 33등 (은메달)
• 정희우, 100 / 53.89 / 59 / 3 / 100 / 31.0, 346.89점, 41등 (은메달)
• 정민찬, 100 / 79.64 / 17 / 3 / 78 / 64.0, 341.64점, 48등 (은메달)

올해는 학생들의 Day 2 성적이 Day 1 성적보다 약간 낮았고, 결국 금메달 / 은메달 경계선에서 뒤쳐진 경우가 많았다. 내가 참가했어도 Day 2 성적이 Day 1보다 낮았을 것 같고, 나도 UCS에서 당황했을 것 같아서, 어느 정도 이해가 된다. 특히 올해 마지막 참가하는 정희우 학생의 경우 대회 종료 5분 뒤에 스핑크스 문제에서 64점을 받았다고 하니 아쉬움이 클 것 같다. 김은성 학생의 경우 대회 종료 후 스코어보드 상 35등의 성적이어서 우리 팀에서는 금메달을 받을 수 없다고 생각했으나, 당시 우리 팀에서 remote participation 팀의 메달 규칙을 당시 제대로 알지 못했고, 결정적으로 중국 팀 학생들이 부정행위로 인해 실격 / 페널티를 받게 되면서 금메달을 얻게 되었다. 축하합니다! 추가적으로 이에 따라 한국은 13년 연속 금메달 수상자가 있다는, 올해 거의 깨질 뻔했던 기록을 이어나간다.

IOI 2024 Day 2에서는 총 3명의 학생이 부정 행위로 실격 / 페널티를 받았다. 세 학생 모두 중국 팀 학생이다. 한 학생은 켜져있는 휴대폰을 들고 대회장에 입장하였으며 화장실도 다녀와서, 당연히 실격을 당하였다. 두 학생은 꺼져있는 휴대폰을 가방에 넣고 대회장에 입장하였는데, 가방을 들고 오는 것도, 휴대폰을 들고 오는 것도 모두 실격 사유이다. 유야무야 넘어갈 법도 했으나 아마 첫 학생 때문에 조사하다가 걸린 것 같다. 꺼진 폰도 켜면 그만이니 부정행위 가능성은 당연히 있고 규정대로면 역시 실격이지만, 이 두 학생은 Day 2 50% 정도로 마무리하였다.

부정행위 실격의 마지막 기억은 IOI 2015에서 대회 서버를 해킹하려는 시도였는데 (슬로베니아 1명 실격), 이번에는 총 3명의 학생이 적발되었고, 특히 실격자는 대회 서버 해킹보다도 훨씬 질이 안 좋은 경우라 유감스럽다고 생각한다. 외부에 공개된 정보가 많지 않고, IC minutes 등 내부 기록이 공개되어야지 구체적 내막을 알 수 있을 것 같다.

이 글을 보는 학생들이 후에 IOI에 (혹은 그냥 아무 중요한 대회에) 참가한다면, 다른 규칙은 다 모르겠지만, 전자 기기를 들고 올 수 있느냐 없느냐의 여부는 당연히 참가자들이 규칙에 맞게 지켜야 한다. 나한테 걸리면 다 실격시킬 테니, 제발 나중에 이상한 말 하지 말자. 물론 IOI 대회장에는 전자 기기 반입이 금지되어 있고, 대표 학생이면 모를 수가 없다고 생각한다. 한편으로 내가 IOI에 참가했을 때는 대회장에 웬만하면 들고 올 수 있는 것이 없었고, 있다면 모두 Practice Session에서 제출 후 검사를 받아야 했던 것으로 기억한다. 저 기억은 오래 되어서 틀릴 수도 있지만, 그래도 주최측에서 관리를 상당히 허술하게 하지 않았나 하는 의심이 들고, 이는 매우 유감스럽다.

이스라엘과 이란은 이번 IOI에 온사이트로 참가하지 못하여서 온라인으로 참가하였다. IOI 2017에서와 동일하게, 메달은 수여되지만 메달 컷오프에는 들지 않는 식으로 처리하였다. (메달 분배는 호스트의 권한이고, 두 팀은 호스트의 대회에 참여하지 않은 것이라 그렇다고 들었다.) 추가로, 이스라엘은 내년부터 러시아/벨라루스와 동일하게 IOI Flag 아래에서 참가하게 된다. GA Meeting에서 다수결로 결정되었다고 들었다.

(upd 24.10.30: 이 글 에서 이스라엘 대표단의 의견을 듣고 이번 IOI에서 이스라엘에 관련된 결정들이 투명한 결정이 아닐 수도 있다고 생각했다. 일단 위에 적은 것은 내가 기억하는 IOI 주최의 공식적인 입장임을 밝힌다.)

중국의 Kangyang Zhou 학생이 Day 2에도 모든 문제를 해결하여서 600점 만점으로 대회를 우승하였다. 1등의 품격답게 부정행위 관련해서도 잡음 없이 깔끔하게 대회를 마쳤다. 축하합니다! 그 뒤를 폴란드의 Adam Gąsienica-Samek (476.22), 미국의 Brian Xue (471.31) 이 따랐다. 문제는 꽤 어려운 편이지만, 그렇게 재미가 있지는 않다. Day 1 문제가 아주 흥미로웠기 때문에 이에 비해서 아쉽다고 생각한다.

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

Day 2 Problems PDF

hieroglyphs-ISC.pdf

0.13MB

hieroglyphs-KOR.pdf

0.28MB

mosaic-ISC.pdf

0.17MB

mosaic-KOR.pdf

0.28MB

sphinx-ISC.pdf

0.21MB

sphinx-KOR.pdf

0.38MB

Problem 4. 상형문자열 (hieroglyphs)

서브태스크 1 (3점)

특정 수 $p, q$ 에 대해서, 이 둘이 inversion 을 이룬다고 생각하자: 다시 말해, $A$ 에서는 $p$ 가 $q$ 보다 먼저 등장하지만 $B$ 에서는 $q$ 가 $p$ 보다 먼저 등장하는, 혹은 그 반대의 경우이다. 이 경우, $[p]$, $[q]$ 가 모두 common subsequence이지만, $[p, q]$ 혹은 $[q, p]$ 는 common subsequence가 될 수 없다. 따라서 UCS는 존재하지 않는다.

inversion이 없으려면, $A = B$ 여야 한다. 이 경우에는 그냥 $A = B$ 가 UCS가 된다.

고로 $A = B$ 면 답은 $A$, 아니면 $[-1]$ 이다.

서브태스크 2 (18점)

문자열 $S$ 와 문자 $c$ 에 대해서 $count(S, c)$ 를 $S$ 에서 $c$ 의 등장 횟수라고 하자. $A, B$ 의 UCS가 $U$ 라고 할 때, $U$ 는 다음과 같은 성질을 만족한다:

Lemma 1. 모든 $c$ 에 대해 $count(U, c) = \min(count(A, c), count(B, c))$
Proof. $U$ 는 $A, B$ 의 common subsequence이니 $\leq$ 가 성립한다. $\min(count(A, c), count(B, c))$ 번 $c$ 를 나열한 수열은 $A, B$ 의 common subsequence이고 $U$ 는 이 수열을 subsequence로 포함해야 하니, $U$ 에서도 최소 $\min(count(A, c), count(B, c))$ 번 $c$ 가 등장해야 하고 고로 $\geq$ 도 성립한다.

서브태스크 2에서는, 모든 $c$ 에 대해 $count(A, c) + count(B, c) \leq 3$ 이 성립한다. 이 사실은 크게 두 가지를 의미하는데:

• $A, B$ 의 LCS를 $O(n \log n)$ 에 계산할 수 있다.
• $U$ 에서 각 문자는 최대 한 번 등장한다.

$A, B$ 의 LCS를 $O(n \log n)$ 에 계산할 수 있는 이유는 이 문제가 LIS 문제랑 상당히 유사하기 때문이다. 구체적으로, $A[i] = B[j]$ 를 만족하는 모든 쌍 $(i, j)$ 에 대해 2차원 좌표평면 상에 점 $(i, j)$ 를 추가하면, 둘의 LCS는 좌표평면상의 점들의 증가하는 체인 에 대응됨을 알 수 있다. 이 때 체인 상에 있는 점들은 $x$ 좌표와 $y$ 좌표가 모두 증가하고, 고로 이 증가하는 체인 의 최대 길이는 LIS를 통해서 계산할 수 있다.

서브태스크 2에서는, $A[i] = B[j]$ 를 만족하는 쌍의 개수가 $O(n)$ 개이며, 각 문자 $c$ 에 대해서 해당 $c$ 가 등장하는 위치를 vector 등으로 저장하면 쉽게 이러한 쌍들을 열거할 수 있다. 쌍들을 모두 $i$ 가 증가하는 순으로 (같을 경우 $j$ 가 감소 하는 순으로) 정렬하자. 이제 쌍에 적힌 $j$ 값을 기준으로 LIS를 구하면, 그것이 두 문자열의 LCS에 대응됨을 알 수 있다. 고로 LIS를 이분 탐색이나 세그먼트 트리 등으로 $O(n \log n)$ 에 계산하고 역추적까지 하면, $A, B$ 의 LCS를 계산할 수 있다. 이를 $L$ 이라고 하자.

만약 문자열 전체의 UCS가 존재한다면, $A, B$ 의 LCS는 분명히 문자열의 UCS가 된다. 고로 이제 문제는 이 LCS가 올바른 답인지 아닌지를 판별하는 것이다. 일단 위 Lemma 조건을 따져보고 만약에 조건을 만족하지 않으면 $[-1]$ 을 반환하자.

조건을 만족하는 경우, $A, B$ 에 공통으로 등장하는 모든 문자는 $L$ 에도 등장한다. 모든 문자 $c$ 에 대해서 $L$ 에서 이 문자가 언제 등장하는 위치를 $ord(c)$ 라고 하자. 어떠한 문자열 $S = {s_1, \ldots, s_k}$ 가 $L$ 의 subsequence가 아니라는 것은, $ord(s_1), \ldots, ord(s_k)$ 가 증가 수열이 아니라는 것과 동치이다. 고로, $ord(s_1), \ldots, ord(s_k)$ 가 증가수열이 아닌 수열이 $A, B$ 의 common subsequence일 수 있으면 $[-1]$, 아니면 $L$ 이 답이다. 여기서 다음 사실을 관찰할 수 있다:

Lemma 2. $k = 2$ 만 해 보면 된다.
Proof. 증가수열이 아닌 수열은 $ord(s_i) > ord(s_{i+1})$ 인 점을 무조건 포함한다. 이 수열이 $A,B$ 의 common subsequence이었다면, ${s_i, s_{i+1}}$ 만 남겨도 여전히 $A, B$ 의 common subsequence이다.

$L = {l_1, l_2, \ldots, l_k}$ 라고 하자. 이제 문제는 다음과 같이 변환된다.

Problem. ${l_j, l_i}$ 가 $A, B$ 의 common subsequence인 $1 \le i < j \le k$ 가 있는지 판별하라.

$A, B$ 에 모두 등장하는 문자 $c$ 에 대해서 $A[i] = B[j] = c$ 인 쌍은 1개 혹은 2개 있다. $L(c)$ 를 이 중 $(i, j)$ 가 사전순으로 작은 쌍, $R(c)$ 를 큰 쌍으로 정의하자 (1개면 $L(c) = R(c)$). 위 문제를 다음과 같이 표현할 수 있다:

Problem. $L(l_j) = (x_1, y_1), R(l_i) = (x_2, y_2)$ 일 때, $x_1 < x_2, y_1 < y_2$ 인 $1 \le i < j \le k$ 가 있는지 판별하라.

이 문제는 $j$ 를 증가시켜나가면서, $R(l_1), R(l_2), \ldots, R(l_{j-1})$ 을 range maximum query 자료구조에 관리하면 (특정 $x$ 좌표에 대한 최대 $y$ 관리) 해결할 수 있다. 전체 시간 복잡도는 $O(n \log n)$ 이다.

서브태스크 4 (34점)

모든 문자 $c$ 에 대해서, $count(A, c) \le count(B, c)$ 일 경우 $A$ 에 등장하는 모든 $c$ 를 마킹하고, 반대의 경우 $B$ 에 등장하는 모든 $c$ 를 마킹하자. 서브태스크 2에서 언급한 Lemma 때문에, 결국 마킹한 모든 문자들은 $U$ 에 등장해야 하고, 또한 그것들만 등장하면 된다.

추가적으로, $A$ 에서 마킹된 문자들은 $U$ 의 subsequence로 등장해야 하고, $B$ 에서 마킹된 문자들 역시 동일하다. $A$ 에서 마킹된 문자들의 집합과 $B$ 에서 마킹된 문자들의 집합은 겹치지 않으니, 최종적으로 $U$ 를 보면, $A$ 에서 마킹된 문자들은 $A$ 에 나온 순서가 유지된 채로 등장하고, $B$ 에서 마킹된 문자들은 $B$ 에 나온 순서가 유지된 채로 등장할 것이다. 즉, $U$ 는 $A$ 와 $B$ 에서 마킹된 문자들의 Interleave 라고 할 수 있다. 다시 말해, 다음과 같은 과정으로 $U$ 를 구성할 수 있다:

• $A$ 에서 마킹된 첫 문자를 골라 $U$ 의 뒤에 붙이고 $A$ 에서 그 문자를 지운다.
• $B$ 에서 마킹된 첫 문자를 골라 $U$ 의 뒤에 붙이고 $B$ 에서 그 문자를 지운다.
• 마킹된 문자가 남아 있을 때까지 반복한다.

Interleave를 할 때, 매 과정마다 $U$ 의 뒤에 붙일 문자가 $A$ 에서 올지 $B$ 에서 올지를 결정할 수 있으면 문제를 해결할 수 있다. UCS가 존재하는 경우 이것을 다음과 같이 결정할 수 있다.

Lemma 3. 현재 $A$ 에서 마킹된 첫 문자를 $i$, $B$ 에서 마킹된 첫 문자를 $j$ 라고 하자. 또한 지금까지 $U$ 를 올바르게 구했다고 하자. ($U$ 에 들어간 $A$ 에서 온 문자들) + $[i]$ + ($B$ 에서 마킹된 문자들) 이 $A, B$ 의 common subsequence 임과, UCS가 $U + [i]$ 의 Prefix임이 동치 이다.
Proof.

• $\leftarrow$: UCS가 $U + [i]$ 의 Prefix면, 그 뒤는 $B$ 에서 마킹된 문자들이 어차피 전부 등장할 것이다.
• $\rightarrow$: 귀류법을 사용한다. UCS가 $U + [j]$ 의 Prefix라고 가정하자. ($U$ 에 들어간 $A$ 에서 온 문자들) + $[i]$ + ($B$ 에서 마킹된 문자들) 는 $A, B$ 의 common subsequence이니 $U$ 의 subsequence여야 한다. 그리디하게 subsequence test를 돌리면, $i$ 는 $j$ 뒤에 등장하니까, $i$ 를 매칭하는 순간 $U + [j]$ 의 prefix를 모두 소모했을 것이다. $j$ 를 손해보았기 때문에, 남은 문자들로 $B$ 에서 마킹된 문자들을 전부 매칭할 수 없다.

고로, 다음 문자를 결정하는 과정은 어떤 문자열이 다른 문자열의 subsequence인지를 결정하는 것으로 귀결된다. Naive하게는, 그리디 알고리즘을 돌려서 $O(n)$ 시간에 판별할 수 있지만, 다음 정보를 전처리해두면 $O(1)$ 시간에 판별할 수 있다:

• $F_A(k)$ : $A$ 에서 마킹된 첫 $k$ 개 문자를 subsequence로 포함하는 $B$ 의 최소 길이 Prefix.
• $F_B(k)$: $B$ 에서 마킹된 마지막 $k$ 개 문자를 subsequence로 포함하는 $A$ 의 최소 길이 Suffix.

고로 $O(n)$ 시간에 전체 문제가 해결된다.

서브태스크 5 (48점)

서브태스크 5는 $n, m$ 이 작다는 것을 제외하면 제약 조건이 없다. 여기까지 왔으면, 답이 되는 후보 하나를 구하는 것은 간단하다: 서브태스크 4의 방법을 써서 UCS의 후보를 $O(n)$ 시간에 구하거나, 아니면 아예 LCS를 $O(n^2)$ 시간에 구할 수도 있다. (만약에 UCS가 존재한다면 UCS는 분명히 LCS가 된다.)

이제 문제는 $A, B$, 그리고 UCS의 후보 $U$ 가 주어졌을 때 이것이 실제로 UCS인지 아닌지를 판별하는 것이다. 문자열 $U$가 UCS가 아니라는 것은,

• $U$ 가 $A, B$ 의 common subsequence가 아니거나
• $A, B$ 의 common subsequence이면서 $U$ 의 common subsequence가 아닌 문자열이 존재한다

첫 번째 조건은 $O(n)$ 시간에 판별할 수 있다. (LCS를 구했으면 판별할 필요도 없겠지만 아마 서브태스크 4의 방식으로 구했으면 판별이 필요할 것이다.) 두 번째 조건이 어려운데, 아래에 이러한 문자열의 존재성을 $O(n^2)$ 시간에 DP로 찾는 방법을 소개한다.

어떠한 문자열이 $U$ 의 subsequence가 아니라는 것은, 이 문자열을 $U$ 에 그리디하게 매칭했을 때 문자열의 모든 문자를 소모하기 전에 포인터가 $U$ 밖으로 나갔다는 것을 뜻한다. 고로 $U$ 의 subsequence가 아닌 것을 찾기 위해서는, 이 포인터 의 위치를 최대화하는 $A, B$ 의 common subsequence를 찾으면 된다.

$dp[i][j]$ 를, $A[0] \ldots A[i-1]$ 과 $B[0], \ldots, B[j-1]$ 의 common subsequence 중, $U$ 에 대한 subsequence test를 돌렸을 때 포인터의 최대 위치 (만약에 $U$ 밖으로 이미 나갔으면 $\infty$) 라고 정의하자. 이 때 전이는 다음과 같다:

• $dp[i+1][j] = \max(dp[i+1][j], dp[i][j])$
• $dp[i][j+1] = \max(dp[i][j+1], dp[i][j])$
• $dp[i+1][j+1] = \max(dp[i+1][j+1], f(dp[i][j], a[i]) + 1)$ if $a[i] = b[j]$
  • $f(j, c)$ 는 $U[j] = c,j \geq p$ 인 최소 위치 (없으면 $\infty$) 를 뜻한다.
  • $a[i]$ 를 common subsequence로 넣었을 때의 그리디 결과라고 생각하면 된다.

$f(j, c)$ 는 $O(n^2)$ 시간에 전처리해서 계산할 수 있다. 고로 전체 문제가 $O(n^2)$ 시간에 해결된다.

만점 풀이

아래 설명할 풀이는 gamegame에게 전해들은 풀이를 완성한 것이다. gamegame은 펜윅 트리만 쓰는 $O(n \log n)$ 풀이라고 소개했는데, 내가 완성한 방법은 $O(n \log^2 n)$ 에 조금 더 복잡한 자료구조를 사용한다. 이 문제의 정해는 $O(n \log n)$ 에 동작하고 아래 설명할 풀이와는 조금 다른 방식인 것 같다.

해결 전략은 위 $O(n^2)$ DP를 관찰과 자료구조를 사용하여 최적화하는 것이다. 이를 위해, 먼저 DP의 계산 순서를 바꾼다. 위에서 설명한 DP는 $(i, j)$ 가 커지는 순서대로 테이블을 채우는데, 여기서는 대조적으로 $dp[i][j]$ 에 적는 값이 증가하는 순서대로 테이블을 계산한다. 구체적으로:

• 초기에 $dp[i][j] = 0$ 인 상태에서 시작한다.
• $f(dp[i][j], a[i]) + 1 = 1$ 인 셀들에 대해서, $x > i, y > j$ 영역에 $dp[x][y] = 1$ 을 칠한다.
• $f(dp[i][j], a[i]) + 1 = 2$ 인 셀들에 대해서, $x > i, y > j$ 영역에 $dp[x][y] = 2$ 를 칠한다.
• $\ldots$
• $f(dp[i][j], a[i]) + 1 = |U|$ 인 셀들에 대해서, $x > i, y > j$ 영역에 $dp[x][y] = |U|$ 를 칠한다.
• $f(dp[i][j], a[i]) + 1 > |U|$ 인 셀이 존재하면 $U$ 가 UCS가 아니라고 판정한다.
• 아니면 $U$ 는 UCS라고 판정한다.

$SN[v]$ 를, 위 프로시저에서 $dp[x][y] = v$ 를 칠한 영역의 집합이라고 하자. $SN[v]$ 를 단순하게 표현하면 $v$ 하나당 $O(n^2)$ 개의 좌표를 저장해야 하지만, 실제 필요한 점들만 (pareto optimal) 저장하는 식으로 저장해야 하는 좌표를 $v$ 하나당 $O(n)$ 개로 줄일 수 있다. 구체적으로, 어떠한 점 $(i_1, j_1)$ 에 대해서 만약 $i_2 \le i_1, j_2 \le j_1$ 인 점 $(i_2, j_2)$ 가 존재한다면, 사실 $(i_1, j_1)$ 은 $SN[v]$ 에 저장할 필요가 없다. 어차피 $(i_2, j_2)$ 의 존재로 $(i_1, j_1)$ 이 존재함을 유추할 수 있기 때문이다.

$S[v]$ 를, 이런 식으로 $SN[v]$ 에서 필요한 점 들만 저장한 점들의 집합이라고 하자. $S[v]$ 를 구하는 것은, $SN[v]$ 를 $(i, j)$ 가 증가하는 순으로 정렬했을 때, $j$ 가 현재까지 본 것중 최소인 점들만 저장하는 식으로 가능하다. $S[v]$ 에는 $i$ 가 같은 두 점이 존재할 수 없어서, 각각의 크기가 최대 $O(n)$ 이다. 하지만, $S[v]$ 의 크기 합은 $O(n^2)$ 라 이 방법은 비효율적이다.

추가적으로, $S[v]$ 를 칠할 때 $U[v - 1] = c$ 였다고 하면, 실제로 $S[v]$ 의 크기는 $\min(count(A, c), count(B, c))$ 이하임 역시 알 수 있다. 답이 되는 $(i, j)$ 는 모두 $A[i-1] = B[j-1] = c$ 라는 성질을 만족하기 때문이다. 하지만 그래도 크기는 각각 $O(n)$ 이라 아직 $S[v]$ 의 크기 합은 $O(n^2)$ 이다.

이제 $S[v]$ 의 크기를 획기적으로 줄일 수 있는 몇 가지 사실을 소개한다. 앞과 동일하게 $U[v-1] = c$ 이고, $U[v],U[v+1], \ldots$ 에서 $c$ 가 총 $K$ 번 등장한다고 하자. 두 가지 Lemma가 성립한다.

Lemma 4. 어떠한 $(i, j) \in S[v]$ 에 대해서 $A[i], A[i+1], \ldots$ 에서 $c$ 가 $K+1$ 번 이상 등장하면서 (AND) $B[j], B[j+1], \ldots$ 에서 $c$ 가 $K+1$ 번 이상 등장하면, $U$ 는 UCS가 되지 않는다.
Proof. $(i, j)$ 로 오는 common subsequence에, $c$ 를 $K+1$ 번 붙인 문자열을 생각해 보자. 이 문자열은 $U$ 의 subsequence가 아니지만, $A, B$ 의 common subsequence이다.

Lemma 5. $U$ 가 $A, B$ 의 common subsequence라면, 어떠한 $(i, j) \in S[v]$ 에 대해서, $A[i], A[i+1], \ldots$ 에서 $c$ 가 $K$ 번 이상 등장하고 (AND) $B[j], B[j+1], \ldots$ 에서 $c$ 가 $K$ 번 이상 등장한다.
Proof. $(i, j)$ 로 오는 common subsequence를 $T$ 라고 하자, 여기에 $c$ 를 $K$ 번 붙인 문자열을 $T + K \times [c]$ 라고 표현하자. $T + K \times [c]$ 는 $U$ 의 subsequence이다. 고로 $A$ 의 subsequence여야 한다. 현재 $(i, j)$ 는 최소점이기 때문에, 점 $i$ 는 $T$ 를 $A$ 에 대해 subsequence test 돌렸을 때 매칭되는 위치가 된다. 만약에 이 뒤에서 $c$ 가 $K$ 번 미만으로 등장한다면, $T + K \times [c]$ 는 subsequence test에서 실패하고, 가정에 모순이다. $B$ 에 대해서도 동일하다.

$A$ 에서 $c$ 의 모든 등장 중 뒤에서 $K+1$ 번째인 것의 위치를 $x_{K+1}$ 라고 하고, $B$ 에서도 동일한 것을 $y_{K+1}$ 라고 하자. Lemma 4/5에 의해, $S[v]$ 의 모든 원소 $(i, j) \in S[v]$ 는 $(i = x_{K+1} + 1), (j = y_{K+1} + 1)$ 중 하나를 만족해야 한다. 고로, $U$ 가 UCS인 이상 $S[v]$ 의 크기는 항상 $1$ 아니면 $2$ 이다.

이제 $S[v]$ 를 구하는 실제 알고리즘에 대해서 생각해 보자.$S[0] = {(0, 0)}$ 이다. $last(v)$ 를, $j < v - 1$ 이면서 $A[j] = A[v-1]$ 인 최대 $j$ (없으면 $0$) 이라고 하자 (선형 시간에 쉽게 계산 가능). Lemma 4 조건이 참이라는 것은, 다음과 같이 쓸 수 있다:

• $S[last(v)], S[last(v) + 1], \ldots, S[v-1]$ 중 $(i \le x_{K+2}, j \le y_{K+2}$) 를 만족하는 점이 존재하는가?

만약에 이러한 점이 존재한다면 $U$ 는 UCS가 되지 않는다. 그렇지 않다면 모든 원소 $(i, j) \in S[v]$ 는 $(i = x_{K+1} + 1), (j = y_{K+1} + 1)$ 중 하나를 만족해야 한다. $i$ 가 고정되었을 때 $j$ 를 최소화하는 원소는 다음 쿼리를 대답하면 해결할 수 있다.

• $S[last(v)], S[last(v) + 1], \ldots, S[v-1]$ 중 $(i \le x_{K+1})$ 를 만족하는 점의 최소 $j$ 는 무엇인가?

다른 케이스도 대칭적으로 동일하다. 최종적으로 $S[0], \ldots, S[|U|]$ 를 다 구한 후 $dp[i][j] = \infty$ 인 점이 있는가를 확인하는 것도 Lemma 4 조건을 보는 것과 유사하게 볼 수 있다.

결국 아래와 같은 자료구조 문제를 해결해야 한다.

• Query: $S[last(v)], S[last(v) + 1], \ldots, S[v-1]$ 중 $(i \le x_{K+1})$ 를 만족하는 점의 최소 $j$ 는 무엇인가?
• Insert: $S[v]$ 의 점 최대 $2$ 개가 주어짐.

$S[v]$ 의 점 $(i, j)$ 를 $(x, y, z) = (i, j, v)$ 와 같은 3차원 점으로 생각하면, 이는:

• Query: $z \geq last(v), x \leq x_{K+1}$ 를 만족하는 점들 중 $y$ 의 최소는 무엇인가?
• Insert: $(x, y, z)$ 가 주어짐.

와 같은 형태가 된다.

이는 2차원 세그먼트 트리를 사용하면 $O(n \log^2 n)$ 에 해결할 수 있다. 첫 좌표인 $x$ 좌표에 대해서 Fenwick tree를 만들고, 각 노드를 $z$ 좌표에 대한 RMQ로 구성하는 식이다. 다만 2차원 세그먼트 트리를 쓰는 것은 느릴 뿐더러 상당히 귀찮으니, 여기서는 비슷한 기능을 지원하는 조금 더 간단한 대안을 소개한다.

$x$ 좌표에 대해서 Fenwick tree를 만드는 것은 동일하지만, 각 좌표를 $z$ 좌표에 대한 monotone stack으로 구성하자. 이 monotone stack은 해당 노드에 대응되는 모든 점들이 $z$ 좌표 증가, $y$ 좌표 증가 순으로 저장되어 있다. 이 문제의 Insert는 $z$ 좌표가 단조적이기 때문에, 이를 스택으로 관리할 수 있다.

삽입을 할 때, 현재 추가하는 점보다 $y$ 좌표가 크거나 같은 점들은 이후 쿼리에 영향을 끼치지 않으니 모두 스택의 뒤에서 제거하고 현재 점을 추가한다. 쿼리를 할 때, $z \geq last(v)$ 인 첫 스택의 점을 구하면, 이 점이 $y$ 좌표 역시 최소화하니, 이 점의 $y$ 좌표를 반환하면 된다. 이 부분에서 이분 탐색이 필요하여, 전체 시간 복잡도는 여전히 $O(n \log^2 n)$ 이지만, 2차원 세그먼트 트리보다는 훨씬 구현이 간단하고 상수 역시 작다.

내가 구현할 때는 $z$ 좌표가 단조적인 줄 몰라서 pareto optimal들을 스택이 아니라 map에 관리했다. 그래도 $O(n \log^2 n)$ 이고, 시간 안에 잘 통과했다.

Problem 5. 모자이크 (mosaic)

서브태스크 2 (12점)

문제 지문에서 샐마가 반복하는 연산은 그냥 다음과 같은 식으로 동적 계획법 테이블을 채우는 것이다:

• $DP[i-1][j], DP[i][j-1]$ 이 모두 $0$ 이면 $DP[i][j] = 1$
• 아니면 $DP[i][j] = 0$

$O(N^2)$ 에 위와 같이 동적 계획법 테이블을 채우고, 반복문으로 $DP[i][j] = 1$ 인 원소의 수를 세면 된다.

서브태스크 3 (19점)

행 $0$ 에 색칠된 내용은 배열 $X$ 이다. 배열 $X$ 의 구간 합을 구하는 문제로, 부분 합 배열을 사용하면 $O(N+Q)$ 에 해결할 수 있다.

서브태스크 4 (29점)

서브태스크 2 풀이처럼 동적 계획법 테이블을 채운 후 2차원 부분 합 배열을 사용하면 $O(N^2 + Q)$ 에 해결할 수 있다.

서브태스크 5 (37점)

컴퓨터로 찍어보면 다음과 같은 규칙을 찾을 수 있다:

• $i \geq 1, j \geq 1, i \text{ mod } 2 = j \text{ mod } 2$ 이면 $1$
• 아니면 $0$

각 쿼리에서 $0$ 번 행과 $0$ 번 열을 빼주면, 결국 행열의 홀짝성이 같은 셀의 개수를 세는 문제가 된다. 만약 쿼리 직사각형 넓이가 짝수면 반을 나눠준 것이 답이다. 홀수면 반을 나누면 정수가 아니라서 올림/내림 해줘야 한다. 직사각형 넓이가 홀수일 경우 직사각형의 꼭짓점의 색이 모두 같다. 그 색이 $1$ 이면 올리고 아니면 내리자.

서브태스크 6 (59점)

서브태스크 5, 그리고 큰 틀에서 전체 문제가 힌트하는 것은, 그냥 컴퓨터로 찍어보면 격자의 규칙이 별로 복잡하지 않다는 것이다. 구체적으로, 다음 사실이 성립한다.

Fact. $i \geq 3, j \geq 3$ 에 대해 $DP[i][j] = DP[i-1][j-1]$

이 사실은 길이 $10$ 이하의 모든 비트열 $X, Y$ 를 brute-force로 나열해 보고 테이블을 찍어본 후 assertion으로 체크하는 식으로 확인할 수 있다. 나는 이런 식의 문제는 읽자마자 그리드를 한번 출력해 봐야 한다고 생각하는 편이다.

이제 이 서브태스크는 $O(N+Q)$ 에 해결할 수 있다. $i \leq 2$ 나 $j \leq 2$ 인 경우에 대해서는 직접 계산해 주고, 그 외 경우는 저것이 성립하게끔 대각선을 타고 점을 보내주면 되기 때문이다.

혹시 증명에 관심이 있다면, 다음을 관찰하면 좋다: $DP[i][j]$ 가 $1$ 이면 무조건 $DP[i+1][j+1]$ 이 $1$이다. $DP[i][j]$ 가 $0$ 이면서 $DP[i+1][j+1]$ 이 $1$ 이려면 $DP[i+1][j-1], DP[i-1][j+1]$ 이 모두 $1$ 이어야 하는데 그런 경우는 격자의 앞쪽에서만 나온다.

서브태스크 7 (78점)

일반성을 잃지 않고 $T[k] \geq 3, L[k] \geq 3$ 을 가정하자. 만약 $T[k] \leq 2$ 일 경우 서브태스크 3과 같이 부분합으로 해결하고, $L[k] \leq 2$ 일 경우 해당 점들은 일일이 세어주자.

서브태스크 6과 같이 $i \le 2, j \le 2$ 인 경우에 대해서 직접 계산을 해 준 후, 다음과 같은 배열을 만들자:
$A = [DP[N-1][2], DP[N-2][2], \ldots, DP[3][2], DP[2][2], DP[2][3], \ldots, DP[2][N-2], DP[2][N-1]]$
한 행에 대한 DP 배열의 구간 합은, 이 배열 $A$ 에 대한 구간 합으로 그대로 대응된다. 고로 $A$ 에 대해서 부분합 배열을 만든 후 문제를 해결할 수 있다.

만점 풀이

여기서도 $T[k] \geq 3, L[k] \geq 3$ 을 가정하자. 삐져나온 점들은 부분합 배열로 세어준다.

쿼리로 주어진 직사각형의 첫 번째 행을, 서브태스크 7과 같이 구간 합으로 대응 시켰을 때 나온 구간이 $[l, r]$ 이라고 하자. 이 경우 두 번째 행에 대응되는 구간은 $[l-1, r-1]$, 세 번째 행에 대응되는 구간은 $[l-2, r-2]$ 와 같은 형태임을 알 수 있다. 쿼리 직사각형의 행이 $k$ 개라고 하면, 우리가 계산하고 싶은 것은:

$\sum_{i = 0}^{k-1} \sum_{j = l-i}^{r-i} A[j]$

$A$ 의 부분합 배열을 $S$ 라고 하면

$\sum_{i = 0}^{k-1} (S[r-i] - S[l-i-1])$

이것을 빠르게 계산하려면 그냥 $S$ 의 부분합 배열을 또 구해주면 된다. 그것을 $SS$ 라고 하면

$SS[r] - SS[r-k] - SS[l-1] + SS[l-1-k]$

고로 $O(N)$ 시간의 전처리로 각 쿼리를 $O(1)$ 에 응답할 수 있다.

Problem 6. 스핑크스 (sphinx)

서브태스크 2 (10점)

각 노드에 대해서 $N$ 번의 실험으로 색을 찾을 수 있다. 지금 색을 찾는 노드의 번호가 $v$ 라고 하자. 모든 $0 \le c \le N - 1$ 에 대해서, $v$ 번 노드를 제외한 모든 노드를 $c$ 로 칠하고, $v$ 번 노드는 $-1$ 로 두자. 컴포넌트가 $2$ 개 이상이면, $v$ 번 노드의 색이 $c$ 가 아닌 것이고, $1$ 개이면, $c$ 인 것이다. 모든 노드에 대해서 반복하면 $N^2$ 번의 실험이 필요하고, 서브태스크 2를 맞을 수 있다.

서브태스크 4 (31점)

이 풀이에서는 각 노드에 대해서 $\lceil \log_2 N \rceil$ 번의 실험으로 색을 찾는다. 지금 색을 찾는 노드의 번호가 $v$ 라고 하자. $v$ 가 아닌 노드들에 $L, L + 1, \ldots, R$ 의 색을 칠한다면 (아무렇게나 칠해도 되는데, 대신 구간의 각 색이 최소 한번은 등장해야 한다), $v$ 의 색이 저 중 하나일 경우 답은 $R-L+1$, 아니면 답은 $R-L+2$ 일 것이다. 고로 $v$ 의 색이 특정 구간에 있는지를 판정할 수 있고, 이를 사용하여 이분탐색을 하면 된다.

서브태스크 3 - 50% 풀이 (47.5점)

모든 $0 \le v \le N - 2$ 에 대해서, $v$ 번 노드와 $v+1$ 번 노드를 $-1$ 로 두고 나머지 노드를 $N$ 으로 칠하자. 이 때의 답을 토대로 $v$ 번 노드와 $v+1$ 번 노드의 색이 다른지를 알 수 있다. 이 여부에 따라서 색을 $0, 1$ 중 하나로 칠해주면, 50%의 점수를 받을 수 있다.

서브태스크 3 (64점)

직선 상에서 $0, 2, 4, 6, \ldots$ 번 노드 (짝수번 노드) 와 $1, 3, 5, 7, \ldots$ 번 노드 (홀수번 노드) 에 대해서 따로 색을 구해주자. 여기서는 편의상 짝수번 노드에 대해서만 풀이를 설명한다.

모든 홀수번 노드에 대해서 색상 $N$ 을 배정하고, 짝수번 노드에 대해서 $-1$ 을 배정하면, 단색 컴포넌트의 개수는 정확히 $N$ 개가 나올 것이다. 비슷하게, 짝수번 노드에서 등장하지 않는 색을 홀수번 노드에 적어도 단색 컴포넌트의 수는 $N$ 개가 나온다. 한편, 홀수번 노드에 짝수번 노드에서 등장하는 색을 적었다면, 같은 색의 두 노드가 인접해지니 단색 컴포넌트의 수는 $N$ 미만이 된다. 이것을 통해, 짝수번 노드에 등장하는 색의 집합을 얻을 수 있다.

응용해서, 홀수번 노드에 특정 색 $c$ 를 적었다면, 짝수번 노드에서 이 색이 어떻게 등장하냐에 따라서 단색 컴포넌트의 개수 역시 알 수 있다:

• $0, N-1$ 번 노드가 $c$ 라면 컴포넌트의 개수가 $1$ 감소한다.
• 그 외 노드가 $c$ 라면 컴포넌트의 개수가 $2$ 감소한다.

편의상 $0, N-1$ 번 노드에 대해서 색을 서브태스크 2처럼 Naive하게 계산해 주면, 결국 위 과정을 통해서 $N$ 번의 실험으로 각 색의 등장 횟수를 구할 수 있다.

이제 실제 해당 색이 어디서 등장하는지를 찾는 것은, 이분 탐색을 통해서 가능하다. 구간 $L, L + 2, L + 4, \ldots, R$ 에 색 $c$ 가 몇 개 등장하는 지의 여부는, 구간에 있는 모든 노드에 $-1$, 구간에 없는 모든 짝수번 노드에 $N$, 그리고모든 홀수번 노드에 $c$ 를 적는 식으로 계산할 수 있다. 가장 앞에 있는 등장부터 이분 탐색으로 찾아주면, 각 위치마다 $\lceil \log_2 (N/2) \rceil$ 번의 실험으로 답을 계산할 수 있다.

앞 예외 처리에 $2N$ 번, 홀수/짝수에서 등장 횟수 세는데 $2N$ 번, 이분 탐색 $7N$ 번으로, $11N$ 번의 실험이 필요하다.

서브태스크 5 - 50% 풀이 (82점)

일반적인 문제에서 50%의 점수를 얻기 위해서는 그래프를 단색 연결 요소 로 분해하는 것으로 충분하다. 단색 연결 요소 를 찾기 위해서 우리는 단색 스패닝 포레스트 를 찾을 것이다. 즉, 단색을 잇는 간선들로 이루어진 그래프에서 스패닝 포레스트를 찾을 것이다. 이렇게 하면 모든 간선을 찾을 필요 없이 최대 $N$ 개의 간선만 고려해 주면 된다.

알고리즘은 재귀적이다. 현재 그래프의 노드가 $N$ 개라면, $N-1$ 번 노드를 제외한 그래프에 대해서 재귀적으로 단색 스패닝 포레스트를 찾아준다. (추가적으로, Union-find를 통해서 실제 단색 연결 요소 역시 관리해 주자). 이제 $N-1$ 번 노드에 인접한 노드들을 보자. 같은 단색 연결 요소를 잇는 간선들은 어차피 스패닝 포레스트에 최대 하나만 들어가니, 여러개가 있다면 아무거나 하나만 남겨주자.

$N-1$ 번 노드에 인접한 노드를 $v_1, v_2, \ldots, v_k$ 라고 하자. 여기서 각 $v_i$ 는 모두 서로 다른 단색 연결 요소에 속한다. 이 중 $N-1$ 번 노드와 색이 같은 노드가 없다면, 문제는 바로 해결이다. 이를 판별하기 위해, ${N-1, v_1, \ldots, v_k}$ 에는 -1, 그들을 제외한 모든 노드에 대해서 $N$ 을 색칠해 주고, 컴포넌트의 개수를 세자. 색 $N$ 으로 이루어진 단색 컴포넌트의 개수는, 우리가 그래프의 정보를 알고 있으니 로컬에서 DFS / Union Find로 세어줄 수 있다. 그러면, 실험으로 주어진 컴포넌트 개수에서, 우리가 세어준 $N$ 이 적힌 단색 컴포넌트의 개수를 빼 줄 수 있다. 뺀 컴포넌트의 개수가 $k+1$ 이면 재귀적 작업은 여기서 끝나고, $k + 1 - m$ 이면, $m$ 개의 노드와 색이 동일하다.

$v_l, v_{l+1}, \ldots, v_r$ 번 노드 중 $N-1$ 번 노드와 색이 같은 노드가 없는지 역시 똑같은 방식으로 셀 수 있다. 고로 색이 동일한 노드가 있다면, 첫 노드부터 순서대로 이분탐색을 통해서 찾아주면 된다. 이렇게 찾은 동일한 노드들에 대해서, 스패닝 포레스트에 간선을 추가해 주고 Union-find를 관리해 준다.

각 정점에 대해 $1$ 번 쿼리, 스패닝 포레스트의 간선에 대해 $1 + \lceil \log_2 N \rceil = 9$ 번 쿼리해서 $10N$ 번의 실험이 필요하다.

만점 풀이

사실 위 50% 풀이는 정확히 $10N$ 번의 실험을 한 것이 아니다. 특히, 단색 컴포넌트의 개수가 많을 수록 실험의 횟수가 줄어든다. 단색 컴포넌트의 개수를 $C$ 라고 하면 스패닝 포레스트의 간선 수는 $N - C$ 이다. 위 50% 풀이는 이 계산에 따르면 $N + 9(N-C) = 10N - 9C$ 번의 쿼리를 했다. 고로, 이후 실제 색을 찾는 과정에서도 $9C + N$ 번의 쿼리가 허용된다.

그래프에 있는 모든 단색 컴포넌트를 하나의 정점으로 압축 (contract) 시켰다면, 모든 간선이 서로 다른 색의 정점을 잇는 그래프로 문제가 변환된다. 이 그래프에서는 서브태스크 3과 아주 유사한 방식으로 답을 구해줄 수 있다. 그래프의 아무 스패닝 트리를 잡은 후, 스패닝 트리에서 깊이가 홀수인 노드와 짝수인 노드들에 대해서 따로 색을 구해주자. 여기서도 편의상 짝수번 노드에 대해서만 풀이를 설명한다.

현재 그래프에 존재하는 짝수 노드들이 $v_1, v_2, \ldots, v_k$ 와 같이 있다면, $v_l, v_{l+1}, \ldots, v_r$ 중 색상 $C$ 인 노드가 존재하는지를 다음과 같이 알 수 있다:

• 모든 홀수 노드에 대해서 색상 $C$ 를 배정
• $v_l, v_{l+1}, \ldots, v_r$ 을 제외한 모든 짝수 노드에 대해서 색상 $N$ 을 배정
• $v_l, v_{l+1}, \ldots, v_r$ 에 대해서 $-1$ 을 배정

만약에 색상 $C$ 인 노드가 존재하지 않는다면, $v_l, \ldots, v_r$ 각각은 크기 1의 컴포넌트를 이룬다. 고로, 실험의 결과는 (위 그래프에서 $C$ 로 이루어진 컴포넌트 수) + (위 그래프에서 $N$ 으로 이루어진 컴포넌트 수) + $r-l+1$ 이 될 것이다. 반면에, 색상 $C$ 인 노드가 존재한다면, 이 노드에 인접한 색상 $C$ 노드가 존재하기 때문에, 그 노드는 컴포넌트에 기여하지 않고, 실험의 결과는 위에서 계산한 것 미만일 것이다.

위 배정에서 $C$, $N$ 으로 이루어진 컴포넌트는, 그래프의 정보를 알고 있으니 로컬에서 DFS / Union Find로 세어줄 수 있다. 이를 활용해서 모든 색상 $C$ 를 시도해 보고, 각 색상에 대해서 이분 탐색으로 모든 등장을 찾아주면 된다.

이와 같이 하면 $9C + 2N$ 번의 쿼리가 필요하다. 각 컴포넌트마다 이분 탐색을 해야 하고, 홀수 / 짝수에 대해서 모든 색상을 각각 다 해보기 때문이다. 이는 총 $12N$ 번의 쿼리를 사용하여 통과하지 않는다. 이분 탐색을 할 때, 특정 짝수 노드의 색상을 찾았다면 이 노드를 이후 탐색에서 사용되지 않도록 아예 리스트에서 지워 버리자. 이렇게 하면 매 이분 탐색에서 필요한 쿼리가 $\lceil \log_2 C \rceil + \lceil \log_2 (C-1) \rceil + \lceil \log_2 (C - 2) \rceil + \ldots$ 와 같은 꼴로 나온다. 컴포넌트를 구하는 $9(N-C)$ 번의 쿼리도 생각해보면 $\lceil \log_2 N \rceil + \lceil \log_2 (N-1) \rceil + \lceil \log_2 (N - 2) \rceil + \ldots +\lceil \log_2 (C+1) \rceil$ 과 같은 꼴이었다. 고로 둘을 다 합하면 $9(N-C) + 9C = 9N$ 이 아니라, $8N$ 정도의 수가 나온다. 이렇게 하면 이제 정말 $11N$ 번의 쿼리를 사용하고, 만점을 얻을 수 있다.