IOI 2021 Day 2

IOI 2021 Day 2 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다.

한국 학생들의 최종 성적은 다음과 같다. 메달 결과는 1금 2은 1동이다.

• 반딧불, 100 / 67 / 70 / 100 / 62 / 75, 474점, 7등, 금메달
• 송준혁, 38 / 37 / 100 / 100 / 50 / 46, 371점, 31등, 은메달
• 최서현, 100 / 9 / 5 / 100 / 89 / 33, 336점, 47등, 은메달
• 장태환, 11 / 37 / 70 / 100 / 11 / 21, 250점, 122등, 동메달

Day 1의 만점자인 Mingyang Deng이 Day 2에서도 만점을 받으며 이번 대회의 우승자가 되었다. 중국은 이번 대회에서 1/2/3/4등을 차지하며 역대 최고 성적을 얻었다. 이보다 더 확실한 우승은 없을 것이다. 사실 이번 대회 최상위권은 잘하는 것으로 유명한 사람들이 많고, 한국의 성인 참가자들이 참여해도 이길 수 있을지 잘 모르겠다. 그런 참가자들 밑에서 당당하게 7등을 차지한 반딧불 학생에게 축하의 말을 전한다.

송준혁, 최서현 학생은 금메달을 정말 아쉽게 놓쳤다. 송준혁 학생은 2019 이온조 (동탑) / 2020 임성재 (은탑) 의 계보를 잇는 또 한번의 은탑을 차지해서 많은 사람들의 안타까움을 샀다. 최서현 학생은 기본적인 서브태스크가 조금 많이 비었다. dungeons 89점도 100점 풀이와 별 차이 없다고 알고 있다. 3금이 충분히 나왔을 것 같아서 나도 아쉽고 학생들도 아쉬울 것 같다. 장태환 학생은 Day 2에서 고생을 많이 했던 것 같다. 은메달은 쉽게 땄었을 것 같다고 생각하는데 대회 경험이 적어서 긴장을 많이 한 것이 아닌가 생각한다. 기회가 많으니 다음에는 좋은 성적으로 돌아올 것이라 생각한다.

코로나19로 인해서 정책적 변동성이 심해지면서, 올해 한국 학생들이 타격을 많이 받았다. 캠프가 비대면으로 진행된다고 하니 학교에서도 교육 시간을 많이 제공하지 않았고 학생들이 대다수의 교육을 학교에서 참가했다. 또한, IOI 날짜가 기말고사 직후로 정해지면서 통상적으로 방학에 진행하던 교육 계획이 깨지고 대다수의 교육을 학기 중에 진행해야 했다. 이 때문에 기말고사 대비와 IOI를 같이 진행한 학생들이 많았고 환경 자체도 교육에 집중하기 힘든 환경이었다. 동일한 이유로 코치 모집도 상당히 힘들었고 굉장히 제한된 인력과 자원으로 IOI 캠프를 진행할 수 밖에 없었다. 상황이 안 좋은 터라 대단히 나쁜 결과가 나올 수 있다고 충분히 예상하면서 교육을 진행하였는데, 다행이도 성적이 그렇게 나쁘지는 않았다. 성적은 전반적으로 "아깝다" 라는 느낌이고 조금만 더 잘했으면 아주 좋은 결과도 얻었을 수 있었을 것 같다. 결과에는 만약이 없지만, 과정 속에서 학생들이 그 나름대로 얻어가는 게 있었으면 좋겠다고 느꼈다.

끝으로 올해 교육에 참가한 학생 모두와 교육을 전담한 신승원 코치, 채점 서비스를 제공한 박수찬 코치에게 큰 박수를 보낸다.

구현한 풀이는 모두 https://github.com/koosaga/olympiad/tree/master/IOI 에서 찾을 수 있다.

dna-ISC.pdf

0.12MB

dna-KOR.pdf

0.16MB

dungeons-ISC.pdf

0.15MB

dungeons-KOR.pdf

0.19MB

notice-ISC.pdf

0.12MB

notice-KOR.pdf

0.16MB

registers-ISC.pdf

0.16MB

registers-KOR.pdf

0.22MB

문제 4. DNA

서브태스크 1 (21점)

먼저 두 문자열에서 A, T, C의 개수가 일치하는지를 확인하고, 일치하지 않는다면 -1을 반환하자.

일치한다면 항상 답이 존재하고, 길이가 커봐야 2이기 때문에 백트래킹으로 답을 구할 수 있다.

서브태스크 2 (43점)

먼저 두 문자열에서 A, T, C의 개수가 일치하는지를 $O(N)$ 시간에 확인하고, 일치하지 않는다면 -1을 반환하자.

$d(A, T)$ 를 주어진 구간에서 $A$ 에서 $T$ 로 바뀌고자 하는 문자의 개수로 정의하고, $d(T, A)$ 도 비슷하게 정의하자. $d(A, T) = d(T, A)$ 이며, $d(A, T), d(T, A)$ 에 속하는 문자들을 서로 바꾸면 두 값이 하나씩 준다. 고로 $d(A, T) = d(T, A) = X$ 를 반환하면 된다. 이는 $O(N)$ 시간에 가능하다.

서브태스크 3 (56점)

두 가지 값을 빠르게 세어야 한다.

• 구간 $[i, j]$ 에서 $c$ 라는 문자의 등장 횟수
• 구간 $[i, j]$ 에서 $c_1 \rightarrow c_2$ 로 바뀌고자 하는 위치의 수

다음과 같은 배열을 관리하자.

• $S_a[c][i] = $ ($a[i] = c$ 이면 1, 아니면 0)
• $S_b[c][i] = $ ($b[i] = c$ 이면 1, 아니면 0)
• $T_a[c_1][c_2][i] = ($$a[i] = c_1, b[i] = c_2$ 이면 1, 아니면 0)

이 경우 위 값은 $S_a[c], S_b[c], T_a[c_1][c_2]$ 라는 배열에서 구간의 합을 구하는 문제가 된다. 이는 부분 합 배열을 계산하면 전처리 $O(N)$, 쿼리당 $O(1)$ 에 구할 수 있다. 자세한 내용은 인터넷 자료를 참고하면 좋다. 이제 서브태스크 2에서 필요한 모든 정보를 쿼리당 $O(1)$ 에 구할 수 있다.

만점 풀이

위의 부분합 배열을 사용하여 두 문자열에서 A, T, C의 개수가 일치하는 지를 확인했고 $d(*, *)$ 를 모두 구했다고 하자. 다음과 같은 그리디 전략이 가능하다.

• 문자가 바뀌지 않으면 무시한다.
• $c_1 \rightarrow c_2, c_2 \rightarrow c_1$ 으로 서로 바뀌는 문자 쌍이 있으면 서로 바꿔준다.
• 위와 같은 문자 쌍을 다 바꾸면 길이 3의 "사이클" 로 문자간의 필요 관계가 형성된다.
  • $d(A, T) = d(T, C) = d(C, A) = X$ 이거나 $d(T, A) = d(A, C) = d(C, T) = X$ 와 같은 식이다.
  • 이 때 $(A, T) / (T, C)$, $(A, C) / (C, A)$ 순으로 풀어주면 (혹은 그 반대) 답은 $2X$ 이다. 이 보다 잘 할수는 없다.

이 그리디 전략은 $O(1)$ 에 구현할 수 있다.

문제 5. 던전 게임

서브태스크 1 (11점)

문제에서 나온 내용을 그대로 구현하면 11점이 나온다. HP가 10000을 넘으면 무조건 인덱스가 증가하는 곳으로 움직이기 때문에, $10000 + n$ 번의 턴 안에 게임은 무조건 끝난다. 같은 이유로 이 문제에서 주인공이 무한 루프를 타는 일은 없다.

서브태스크 2 (37점)

서브태스크 1과 동일한 이유로, HP가 $10^7$ 을 넘어가면 더 이상 지는 일은 없다.

만약 플레이어가 $i$ 번 방에서 패배했을 경우, $x < s[i]$ 였던 HP가 $x + s[i]$ 가 된다. 이는 $2x$ 보다 크기 때문에, 패배했을 경우 항상 HP가 두 배 이상 커진다는 뜻으로 해석할 수 있다. 고로, 플레이어가 패배하는 경우는 많아야 $\log 10^7 = 23$ 번 뿐이다.

대부분의 경우 플레이어는 승리하니, 승리하는 상태를 기본으로 두고 패배하는 특별한 상황을 탐색하는 식으로 접근하자. $n+1$ 개의 정점에 대해서, 승리했을 때 움직이는 정점과 가중치를 간선으로 표현하면, $n$ 번 정점을 루트로 한 Directed tree가 나온다. 현재 HP가 $x$ 인 경우, 정점 $v$ 에서 출발해서 처음으로 패배하는 지점은, $depth[v] - depth[w] + x < s[w]$ 가 만족한다.

이제 문제는, $v$ 에서 루트로 가는 경로에서 처음으로 해당 조건을 만족하는 $w$ 를 빠르게 찾는 자료 구조 문제가 된다. $x + depth[v] < s[w] + depth[w]$ 로 식을 전개하면, 이는 경로 상 최댓값이 처음으로 특정 수를 넘는 지점을 찾는 문제이다. $s[v] + depth[v]$ 값을 Sparse table에 담으면, $v$ 번 정점에서 $2^i$ 개의 Ancestor를 보았을 때 해당 값의 최솟값을 찾을 수 있다. 이 정보를 토대로 이분 탐색을 하면 된다. 시간 복잡도는 $O(n \log n + q \log X \log n)$ 이다.

서브태스크 3 (50점)

$S = s[i]$ 가 동일하기 때문에, 위치와 상관없이 HP만으로 승패 여부를 판단할 수 있다. 또한, 처음에는 패배만 하다가, 한번 승리하게 되면 그 순간부터는 계속 승리할 것이다.

한번 승리하기 시작한 케이스는 간단한 편이다. $dp[v]$ = ($v$ 에서 항상 이기기만 할 때, $n$ 에 도달하면서 얻는 HP) 라고 정의하자. $dp[v] = dp[w[v]] + S$ 라는 간단한 점화식으로 위 DP를 구할 수 있다. HP가 $S$ 를 넘어가면 위 값을 사용하여 바로 $n$ 으로 보내주자.

패배하는 경우에는 사이클이 존재하며, 처음 승리한 시점도 같이 알아야 해서 조금 더 복잡하다. Sparse table을 사용하면 되는데, 정점 $v$ 에서 $2^i$ 번 패배하였을 때 도달하는 정점, 그리고 그 때 얻는 HP를 관리한다. 이 경우, 초기 지점에서 몇 번의 패배 끝에 승리 상태로 도달할 수 있는지, 그리고 그 때의 최종 상태는 언제인지를 이분 탐색으로 알 수 있다.

시간 복잡도는 $O(n \log X + q \log X)$ 이다.

서브태스크 4 (62점)

서브태스크 3의 풀이를 조금 더 확장하면 된다.

등장하는 $s[i]$ 의 값을 크기 순으로 $S_1, S_2, S_3, S_4, S_5$ 라고 할 때, 다음과 같은 6개의 State를 생각해 보자.

• 현재 HP가 $S_1$ 미만인 상태
• 현재 HP가 $S_1$ 이상 $S_2$ 미만인 상태
• ...

현재 HP가 $S_1$ 미만인 경우는 서브태스크 3의 패배 케이스와 동일하고, $S_5$ 이상인 경우는 승리 케이스와 동일하다. 그 사이도 그동안 알던 것에 비해서 크게 다르지 않다. HP가 해당 구간에 있다면 어떤 정점에서 승리하고 패배하는 지가 명확히 결정되기 때문에, 이를 결정한 다음에 패배 케이스에서 사용했던 것과 동일한 Sparse table을 구성하면 된다. 이제 초기 지점에서 몇 번의 승리/패배 끝에 다음 상태에 도달할 수 있는지를 이분 탐색으로 해결하면 된다.

서브태스크 5 (89점)

서브태스크에 힌트가 굉장히 많아서 만점 풀이를 떠올리는 게 자연스러운 편이다. 사실, 만점 풀이 자체로 보면 어렵고 독특한 아이디어라고 생각하는데, 서브태스크가 상당히 친절해서 접근하기 상대적으로 수월하지 않았나 싶다.

서브태스크 4와 같이 State를 나누는데, 이번에는 각 state의 크기를 HP의 $\log_2$ 값에 따라 나눈다. $i (0 \le i \le 24)$ 번 State는 HP가 $[2^i, 2^{i+1} - 1]$ 구간에 있는 상태라고 정의하자. $s[v]$ 의 값에 따라서 주인공의 행동은 다음과 같이 변한다.

• $s[v] \le 2^i$ 인 경우 HP가 구간 안에 들어 있으면 무조건 이긴다. 고로 다음 위치가 결정된다.
• $s[v] \geq 2^{i+1}$ 인 경우 HP가 구간 안에 들어 있으면 무조건 진다. 고로 다음 위치가 결정된다.
• 그 외 경우 HP가 구간 안에서 어떤 값인지에 따라서 승패가 결정된다.

세 번째 경우에는 다음 위치가 결정되지 않는다. 여기서 서브태스크 2와 같은 관찰을 할 수 있는데, 만약 $2^i < s[v] < 2^{i+1}$ 인 상태에서 이기게 된다면, 그 다음에는 무조건 HP가 $2^{i+1}$ 을 넘어가게 된다. 즉, 기본적으로 진다고 생각하고 다음 위치로 따라가다가, 만약 $2^i < s[v]$ 가 만족하는 $v$ 가 발견된다면 여기서 이기고 바로 위 State로 넘어가는 것이다.

결론적으로 모든 위치에 대해서 다음 위치가 결정되며, State를 벗어날 수 있는 경우는

• $s[v] > 2^i$ 인 $s[v]$ 에게 이기거나
• 다음 위치를 따라가다가 현재 HP가 $2^{i+1}$ 이상이 되거나

의 두 가지밖에 없다. 각 쿼리에 대해서 이 두 가지 상황 중 빠른 상황이 언제 도달하는 지를 찾을 수 있다면, 레벨을 한 단계씩 올라가면서 문제를 해결할 수 있다.

이는 각 레벨 $i$에 대해서 Sparse table을 만들어서 해결 가능하다. 서브태스크 3/4와 마찬가지로, 정점 $v$ 에서 $2^j$ 번 다음 상태로 움직였을 때 도달하는 정점 $nxt[i][j][v]$, 그리고 그 때 얻는 HP $sum[i][j][v]$ 를 관리한다. 추가적으로, 정점 $v$ 에서 $2^j$ 번 다음 상태로 $s[v] > 2^i$ 인 $s[v]$ 에게 매번 지면서 갈 수 있는 최대 HP를 정한다. 이를 $threshold[i][j][v]$ 라고 하면,

• $nxt[i][j][v] = nxt[i][j-1][nxt[i][j-1][v]]$
• $sum[i][j][v] = sum[i][j-1][v] + sum[i][j-1][nxt[i][j-1][v]]$
• $threshold[i][j][v] = min(threshold[i][j-1][v], threshold[i][j-1][nxt[i][j-1][v]] - sum[i][j-1][nxt[i][j-1][v]])$

와 같은 점화식이 성립함을 볼 수 있다. 이제 Sparse table에 이분 탐색을 하여 State를 벗어나는 첫 지점을 계산할 수 있고, 이를 모든 레벨에 대해서 반복하면 89점을 얻는다.

만점 풀이

만점 풀이는 서브태스크 5와 똑같지만, 이상하게 $n \le 400,000$ 이라는 큰 제한이 붙어서 메모리 최적화를 조금 해야 한다. 상황에 따라 시간 최적화도 필요할 수 있다. 다음과 같은 방법들이 있다.

• 일단 long long을 사용하지 않고 int만을 사용하여 위 테이블을 관리할 수 있다. 이 경우 $400000 \times 25 \times 25 \times 3 \times 4b = $ 3GB의 메모리를 사용한다.
• $j < i$ 인 경우만 관리하여도 아무 문제가 없다. 테이블을 잡을 때 $400000 \times 625$ 를 잡는 대신 $400000 \times 25(25-1)/2 = 400000 \times 300$ 의 크기를 잡으면 $400000 \times 300 \times 3 \times 4b = $ 1.44GB의 메모리를 사용한다. 아마 이 정도로 하면 통과될 것이다.
• 시간과 Tradeoff를 하면서 메모리를 줄일 수 있다. 레벨을 $2^i$ 기준이 아닌 $8^i$ 기준으로 해도 위와 같은 논리가 거의 동일하게 성립한다. 위에서는 $s[v] \geq 2^{i+1}$ 인걸 따로 처리해 줘야 한다는 식으로 설명했지만, $s[i] \le 2^i$ 인 경우는 무조건 이기고, 그 외의 경우는 무조건 진다고 생각해 줘도 이야기가 달라지지 않는다. 고로 $2$ 를 다른 숫자로 바꾸면서 메모리와 시간을 조정할 수 있다. 다만, 한번 이긴다고 바로 다음 레벨로 가는 건 아니고, 여러 번 (최대 7번) 이겨야 다음 레벨로 갈 수 있으니, 이 부분을 지원하게끔 구현해 줘야 한다. 이렇게 하면 $400000 \times 25 \times 8 \times 3 \times 4b =$ 900MB의 메모리를 사용한다.
• HLD를 사용하면 메모리 $O(n \log X)$, 시간 $O(n \log X + q \log n \log X)$ 에도 풀 수 있으나 구현이 위 풀이의 한 4배는 되는 것 같다.

문제 6. 레지스터

$s = 0$, $q \le 9n$ (33점)

두 레지스터 $a, b$ 를 받아서, $a = min(a, b)$ 를 저장하는 함수를 구현할 것이다. a = min(a, b) 는 $a > b$ 일 때 $a$ 에 $b$ 를 대입하는 함수이다. 즉

• 특정 조건이 만족하는 지를 확인해야 하고 ($a > b$)
• 그 조건이 만족하면 대입

하는 작업을 수행해야 한다. 일반적인 프로그래밍 언어에는 if 문이 존재하지만, 이 언어에서는 존재하지 않는다 (if 문은 goto나 jmp 를 사용하여 구현되니 직접 짤 수도 없다). 고로 이 과정을 구현하는 것이 단순하지 않다.

$a > b$ 를 구현하기 위해서는 이진수 체계에 대해서 어느 정도 아는 것이 좋다. a > b 는 0 > b - a 와 동일하며, -a = (~a) + 1 이라는 식을 만족한다. 고로 b + 1 + (~a) 를 계산한 후 이것이 음수인지 양수인지를 확인하면 된다. 이 문제에서는 unsigned int 형식이라 원론적으로는 모든 수가 양수이나, 실질적으로 1999 번째 비트가 켜져 있으면 해당 수는 음수라고 보는 것이 맞다. 고로

• 초기에 상수 1 을 레지스터에 저장
• c := b + 1 + (~a) 를 add, not 연산을 사용하여 구현
• 1999 번째 비트가 켜져 있는지 확인

하는 식으로 구현할 수 있다.

두 번째로는 위 조건이 만족하였을 때 수를 대입하는 작업이 필요하다. 우리가 다루는 수의 크기가 작기 때문에, c의11 ~ 1999 번째 비트는 모두 켜져 있거나 꺼져 있다. 고로 c = (c >> 1000) 연산을 적용하면, 맨 아래 1000개 비트가 모두 켜져 있거나 꺼져 있는 상태를 얻을 수 있다. 이 상태에서, c = c & (a ^ b) 를 적용하면, c 는 a > b 일 때 a ^ b이고, a <= b 일 때 0이다. 고로, a = (a ^ c) 를 적용하면 이는 a = min(a, b) 를 대입한 것과 똑같은 상태가 된다.

이 함수가 구현되었다면 전체 문제는 다음과 같이 해결 가능하다. 99 번 레지스터에 a[0] 을 대입한 후, 모든 $1 \le i \le n - 1$ 에 대해서, 98 번 레지스터에 a[i] 를 대입한 이후 r[99] = min(r[99], r[98]) 을 호출하자. 구현에 따라 다르겠지만, 본인의 경우 아마 $q = 9n - 5$ 가 나왔던 것 같다. 이렇게 하면 서브태스크 3까지 통과할 수 있다.

$s = 0, q \le 5 + 15 \lceil \log n \rceil$ (58점)

$9n$의 앞에 붙는 상수를 줄이는 것으로는 승산이 없을 가능성이 높다. 위에서 설명한 연산들이 거의 다 비트 연산이라는 점을 활용하여, 여러 숫자들에 대해서 $a_0 = min(a_0, a_k), a_1 = min(a_1, a_{k+1}) \ldots $ 을 동시에 해 줄 수 있다. 이 연산을 통해 우리는 $2k$ 크기의 배열을 $k$ 로 줄일 수 있다. 고로 이를 $\lceil \log N \rceil$ 번 반복해주면 $a_0$ 은 최솟값이 된다. 이는 문제 제약 조건에 따르면 최대 7번이다.

시작하기 전에 $N = 2^m$ 를 가정하자. $N$ 이상의 가장 작은 $2^m$ 를 직접 계산한 후, $a_N, a_{N + 1} \ldots, a_{2^m-1}$ 을 모두 $2^k - 1$ 로 채워주면 된다. 이는 두 번의 연산으로 가능하다.

$X = a_0 a_1 \ldots, a_{p-1}$, $Y = a_p a_{p+1} \ldots, a_{2p-1}$ 가 있을 때, 위에서 시도했던 것처럼 $Y - X$ 를 계산해 보자. 만약 이 수의 $pk$ 번째 비트가 1이라면, $a_{p-1} \ge a_{2p-1}$ 이 성립함을 알 수 있다. $a_{p-1} = a_{2p-1}$ 일 경우 아래에서 생긴 받아올림에 따라서 결과가 달라질 수 있지만, 해당 경우에는 어떤 결과가 나오든 상관이 없다. 같은 식으로, $(p-1)k$ 번째 비트에서 받아올림이 발생했다면, $a_{p-2} \ge a_{2p-2}$ 가 성립한다. 일반화하여, $k(i+1)$ 번째 비트에서 받아올림이 생겼다면, $a_i \ge a_{p+i}$ 이 성립한다. 이 때, 받아올림이 생겼는지 여부는 (Y - X) ^ X ^ Y 의 비트를 보면 알 수 있다.

Z = (Y - X) ^ X ^ Y 를 계산한 후, $k, 2k, \ldots, pk$ 번째 비트만이 켜진 숫자와 AND 를 취해서 받아올림만을 가져가자. $k$ 번째 비트가 켜졌다면 $0 \ldots (k-1)$ 이 켜져 있고, $2k$ 번째 비트가 켜졌다면 $k \ldots (2k-1)$ 이 켜져 있는 레지스터를 얻을 수 있다. C = Z - (Z >> k)를 취하면 위와 같은 레지스터를 얻을 수 있다.

이러한 레지스터 C 를 얻었다면, C = C & (X ^ Y) 를 통해서 $a_i \ge a_{i + p}$ 인 위치에서만 X^Y 의 비트가 저장된 레지스터를 얻을 수 있고, 이것을 X = X ^ C 로 적용시키면 문제가 해결된다.

구현에 따라서 어떠한 $q$ 를 얻을 지는 조금 다르겠지만, 본인은 $q = 5 + 15 \lceil \log n \rceil$ 이라는 값을 얻었다. 절묘한 차이로 서브태스크 2의 예외 처리를 건너뛰고 $s = 0$ 인 경우를 모두 해결할 수 있다.

$s = 1, q \le 4n^2$ (71점)

정렬의 기본은 $a > b$ 일 때 $a, b$ 를 바꾸는 것이다. 이를 수행하는 함수를 구현할 것인데, 이는 33점 풀이에서 a = min(a, b) 를 구현한 것과 거의 동일하게 할 수 있다. 우리는 c = (a > b ? (a^b) : 0) 이라는 값을 계산할 수 있기 때문에, 이 값을 $a, b$ 두 값 모두 에 XOR 해 주면 a = min(a, b), b = max(a, b) 가 저장되게 된다. 적당히 0번 레지스터에 있던 값을 $0 \ldots n-1$ 번 레지스터에 뿌려준 후, 위 함수를 사용하여 버블 소트를 구현하면 된다. 이것도 구현에 따라 다르겠지만, 본인은 정확하게 $q = 4n(n-1) + 4n - 3 + 3 = 4n^2$ 가 나왔다.

$s = 1, q \le 22n$ (100점)

위 서브태스크의 관찰을 종합하면, $(a_0, a_k), (a_1, a_{k+1}), \ldots, (a_{k-1}, a_{2k-1})$ 쌍에 대해서, $a > b$ 일 때 $a, b$ 를 바꾸는 것을 동시에 할 수 있다. 71점에서 했던 것처럼, $X, Y$ 두 값 모두에 $C$ 를 XOR 해 주면 된다.

이 관찰을 활용하여 정렬을 효율적으로 할 수 있을까? 일단 문제점은, 인접한 쌍이 아니라 $k$ 만큼 거리가 떨어진 쌍에 대해서만 동시에 스왑이 가능하다는 점이다. 한편, 우리는 $(a_{k+1}, a_0), (a_{k+2}, a_1), (a_{k+3}, a_2)$ 에 대해서도 위 연산을 동시에 할 수 있다. 이제 전체 배열을 $a_k - a_0 - a_{k+1} - a_1 - a_{k + 2} - a_2 \ldots$ 와 같이 나열해 보자. 예를 들어,

• $n = 8$ 이면 $4 - 0 - 5 - 1 - 6 - 2 - 7 - 3$
• $n = 9$ 이면 $4 - 0 - 5 - 1 - 6 - 2 - 7 - 3 - 8$

이렇게 나열하였을 때 우리가 하는 연산은

• $4 - 0, 5 - 1, 6 - 2$ 과 같이 홀수번째 인접한 원소를 교환
• $0 - 5, 1 - 6, 2 - 7$ 과 같이 짝수번째 인접한 원소를 교환

으로 환원이 된다. 고로 우리가 이 연산들을 적절히 활용해서 정렬할 수 있다면, 위에서 나열한 순서 ($a_4, a_0, a_5, a_1 \ldots $) 대로 작은 원소부터 큰 원소가 나열이 될 것이다. 이는 정렬이 끝난 후 우리가 Reorder하면 되기 때문에, 이제 문제는 홀수번째 / 짝수번째 인접한 원소를 교환하여 전체 배열을 정렬하는 문제로 환원된다.

우리가 가진 방법이 홀수 / 짝수번째 원소를 한 번에 교환하는 것이니, 이것으로 다음과 같이 버블 정렬과 비슷한 알고리즘을 만들면 될 것 같다는 희망사항을 가질 수 있다.

Lemma. 버블 소트의 $i$ ($0 \le i \le n - 1$) 번 pass에서는 $j = 0, 1, \ldots, n - 2$ 에 대해 순차적으로 a[j] > a[j+1] 일 경우 swap(a[j], a[j+1]) 을 수행한다. 이 때, 만약 $i$ 가 홀수일 때는 홀수 $j$ 만, $i$ 가 짝수일 때는 짝수 $j$만 고려해 줘도 된다. 즉:

• $i = 0, 2, 4 \ldots$ : swap(a[0], a[1]), swap(a[2], a[3]), ...
• $i = 1, 3, 5 \ldots$: swap(a[1], a[2]), swap(a[3], a[4]), ...

이 희망 사항은 실제로 참이며, 로컬에서 Brute force 등으로 검증할 수 있다. 고로 이를 구현하면 100점을 얻을 수 있다.

실제 증명은 조금 복잡한 편으로, 아래에 그 증명을 서술한다.

Proof. 증명은 위키백과 에서 가져왔다. $a[i]$ 의 원소가 0 혹은 1로만 이루어져 있다고 가정하자 (Knuth's Zero-One Principle). 이 수열에 있는 1의 개수가 $e$ 라고 하고, 각 1들을 $one_0, one_1, \ldots, one_{e-1}$ 라고 부르자.

$one_{e-1}$ 의 경우에는 0/1번째 pass 중 한 번 오른쪽으로 움직일 것이고, 이후 모든 pass에서 항상 오른쪽으로 움직일 것이다. $one_{e-1}$의 시작 위치는 $e-1$ 혹은 그보다 오른쪽이며, 종료 위치는 $n-1$ 이다. 고로 $(n - e) + 1$ 번의 pass를 거치면 무조건 올바른 위치에 머무른다.

$one_{e-1}$ 이 최대 1개의 pass 이후 항상 오른쪽으로 움직였다는 것은, 그 이후 한번도 $one_{e-2}$ 와 비교된 적이 없다는 것이다. 다른 말로, $one_{e-2}$ 는 첫 1번의 pass 이후, 목적지에 도달하기 전까지는 $one_{e-1}$ 을 신경쓸 필요가 없게 된다. 첫 pass에서는 $one_{e-1}$ 때문에 이동하지 못할 수 있고, 이후 parity가 맞지 않아 또 하나의 pass를 놓칠 수 있다. 최대 2번의 pass를 놓친 이후 $one_{e-2}$ 는 사실상 남은 1들 중 가장 오른쪽에 있다. 고로 $(n - e) + 2$ 번의 pass를 거쳐서 올바른 위치에 머무른다.

이 논리를 반복하면, $one_i$ 는 최대 $(n - e) + (e - i)$ 번의 pass를 거친 이후 올바른 위치에 머무른다. $n - i \le n$ 이니, $n$ 번의 pass로 충분하다.

문제 풀이 한 줄 요약

• candies: 수열에 직접 쿼리를 적용하는 것이 아니라 쿼리에서 수열의 값을 이끌어 낸다는 발상의 전환. 그리고 수열에 값에 대한 관찰 이후 Segment tree를 사용하여 오프라인으로 해결
• keys: $S_i \subseteq S_j$ 라는 관계의 일부를 추려낸 후 functional graph를 만들어서, 관계가 동일한 경우를 반복적으로 contract시켜줌. 이 과정에서 Heavy light decomposition와 같이 작은 집합을 큰 집합에 합쳐주는 아이디어를 현명하게 적용해야 함. Two Chinese Algorithm이라고 알려진 Directed MST의 효율적인 해결 방법과 유사
• parks: 각 체인에 굴곡이 많은 스패닝 트리일 경우 매칭이 항상 존재함. 또한 이 문제에서 요구하는 매칭은 특수하기 때문에 일반적인 Bipartite Matching보다 효율적인 방법으로 계산할 수 있음. Planar graph의 Cut-cycle duality와 수학적 귀납법을 사용하여 증명할 수 있음 (최소 반례를 가정하였을 때 모순을 보임.)
• dna: 부분합을 전처리하여 빠르게 구한 후 간단한 Greedy 전략을 사용하여 해결.
• dungeons: 현재 값의 $\lfloor \log_2 \rfloor$ 에 따라서 25개의 Level로 상태를 나누고, 각 상태를 흔히 Sparse table이라고 부르는 DP를 통해서 전처리. 각 쿼리마다 이 Sparse table을 사용하여 다음 상태로 움직이거나 아니면 이동을 종료.
• registers: 실제 SIMD 연산을 사용하여 극히 효율적인 Sorting network를 구현하는 것과 비슷한 문제. 문제에서 주어지는 assembly 언어의 부분집합을 사용하여 최솟값과 정렬을 구현해야 함. 뺄셈에서 사용되는 이진수 표현을 현명하게 활용하여서 최댓값과 최솟값을 분리할 수 있고, 이 표현을 병렬화하면 버블 정렬도 $O(n)$ 의 연산에 구현할 수 있음. 더 복잡한 Sorting network (Batcher's odd-even mergesort) 를 사용하면 $O(\log^2 n)$ 정도의 연산에도 해결할 수 있으나 문제에서 요구되지 않음.