koosaga's profile image

koosaga

July 5, 2021 22:00

IOI 2021

algorithms, , ioi, , graph, , assembly

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

이 글에서는 해당 대회에 출제된 문제들을 하나 하나 풀어보고, 그 풀이를 소개한다. IOI에는 다양한 문제가 나오기 때문에 모든 풀이를 하나의 주제로 요약할 수는 없다. 고로 각 풀이의 핵심 키워드를 아래에 정리하였다.

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

문제 풀이 한 줄 요약

  • 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)$ 정도의 연산에도 해결할 수 있으나 문제에서 요구되지 않음.

문제 1. 사탕 분배

서브태스크 1 (3점)

사탕의 개수를 배열에 저장한 후 문제에서 요구하는 사항을 구현하면 된다. 시간 복잡도는 $O(NQ)$ 이다.

서브태스크 2 (11점)

사탕을 쌓기만 하니 박스가 빌 걱정을 하지 않아도 된다. 또한, 사탕이 용량을 초과하는 문제점은 매 쿼리마다 해결할 필요가 없다. 모든 쿼리를 처리한 후에 용량을 초과하는 사탕을 빼 줘도 무방하다.

고로, 구간에 특정 수를 더하는 쿼리를 여러 번 처리하면 문제를 해결할 수 있다. 이는 여러 가지 방법으로 해결할 수 있는데, 가장 간단한 방법은 변홧값 배열이다. 이 기법에 대해서는 인터넷에 좋은 설명이 많으니 검색해 보기 바란다. 시간 복잡도는 $O(N+Q)$ 이다.

서브태스크 3 (38점)

$C_i$ 가 일정하기 때문에, 구간에 다음 두 연산을 적용할 수 있으면 된다.

  • $A_i := A_i + X$
  • $A_i := min(A_i, Y)$

이를 지원하는 자료구조를 고안하는 문제로, 여기서 크게 두 가지 풀이를 알고 있다.

첫 번째 풀이는 사전지식을 사용하는 풀이이다. Segment Tree Beats라는 자료구조가 위 두 연산을 지원한다. 본인은 이 글과 이 동영상을 보고 Segment Tree Beats를 익혔던 것 같다. 둘 다 좋은 자료이니 한번 보는 것을 추천한다. 위 자료구조를 알고 있으며 구현에 익숙하다면 날로 먹기 아주 좋은 풀이이다.

두 번째 풀이는 여기에 조금 더 아이디어를 사용한다. 구간에 적용하는 함수의 꼴을 $f(x) =max(C, min(x - A, B))$ 형태로 표현하면, $f(g(x))$ 역시 $max(C, min(x - A, B))$ 형태로 나옴을 계산할 수 있다. 이를 사용하면 구간에 함수를 적용시키는 문제가 되니 $f(x)$ 를 Lazy propagation으로 관리할 수 있게 된다. 아마 이런 아이디어에서 출발하면 서브태스크 4의 풀이도 나온다고 (그리고 결론적으로 전체 문제가 sqrt 시간에 풀린다고) 들었다.

만점 풀이

만점 풀이는 그다지 어려운 자료구조를 사용하지 않는다. 다만 오프라인 쿼리라는 점을 적극적으로 활용하며, 발상의 전환을 요구한다.

수열에다가 쿼리를 적용한다고 생각하지 않고, 쿼리의 결과에서 숫자를 찾아낸다고 생각하자. 예를 들어서, $N = 1$ 이라고 하였자. 쿼리로 $+v[1], v[2], +v[3], -v[4]$ 형태의 수들이 들어왔을 때, 이것들을 직접 시뮬레이션하지 않고도 $A[1]$ 의 최종 결과를 알 수 있는 방법이 있을까? 만약 이 $A[1]$ 의 결과를 예쁘게 표현할 수 있다면, 전체 문제는 $A[i]$ 의 인덱스가 증가하는 순서대로 스위핑하면서 풀 수 있다.

  • 각 쿼리에 대해서 “현재 쿼리가 가지고 있는 $v[j]$” 값을 저장한다. 초기에는 전부 0이다.
  • $i$ 에서 $i+1$ 번 점으로 넘어갈 때, 시작점이 $i + 1$ 인 쿼리들의 $v[j]$ 값을 입력으로 주어진 값으로 설정한다.
  • 반대로, 끝점이 $i$ 인 쿼리들의 $v[j]$ 는 0으로 맞춰줘서 실질적으로 지워버린다.

이렇게 할 경우, 배열에 $O(Q)$ 번의 변화만으로 현재 가지고 있는 쿼리의 리스트를 시간순으로 관리할 수 있다. 만약 $A[1]$ 의 최종 결과가 세그먼트 트리등으로 관리 가능한 값이라면, 매 지점마다 적절한 쿼리로 답을 구할 수 있으니 전체 문제가 효율적으로 해결될 것이다. 이제 목표는, 세그먼트 트리로 관리하기 쉬운 형태로 $A[i]$ 의 최종 결과를 표현하는 것이다.

이러한 문제는 일반적으로 각 수의 변화 형태를 그래프로 그리면 좋다. 쿼리 시간을 $x$ 축, 값을 $y$ 축으로 하고 값의 그래프를 그려보자. 이 때, 문제의 조건과 상관없이, 값이 0 미만으로 떨어지거나 $C[i]$ 를 넘는 것은 고려하지 않고, 그대로 현재까지 들어온 값의 합만 그래프로 그려주자. 즉, 그래프는 $(i, \sum_{j = 1}^{i} v[j])$ 점들을 잇는 꺾은 선이다.

일단 $C[i]$ 가 무한히 크다고 가정하고 관찰해보자. 만약 $C[i]$ 가 무한히 크다면, 현재 배열의 값은 $\sum_{j = 1}^{q} v[j]$ - (그래프 상 최저점의 $y$ 좌표) 이다. 최저점에 도달했을 때는 무조건 0개의 사탕이 있는데, 그 이후로는 사탕이 바닥나는 일은 없기 때문이다. $C[i]$ 가 적당히 작더라도, 만약에 그래프 상 최고점과 최저점의 높이 차가 $C[i]$ 이하라면, 동일한 논리가 성립한다.

만약 두 점의 높이차가 $C[i]$ 초과라면 어떻게 될까? 일단, 그래프 상에서 최고점과 최저점의 높이 차가 $C[i]$ 이하로 유지되는 가장 긴 suffix를 찾은 후, 이 suffix의 바로 왼쪽 값을 넣어주자. 이 경우, 가장 왼쪽 값을 넣으면 suffix의 높이 차는 $C[i]$ 초과, 안 넣으면 $C[i]$ 이하가 된다. 만약

  • 가장 왼쪽 값이 최댓값이라면: 현재 배열의 값은 $\sum_{j = 1}^{q} v[j]$ - (구간 상 최저점의 $y$ 좌표) 이다. 최저점에 도달했을 때는 무조건 0개의 사탕이 있기 때문이다.
  • 가장 왼쪽 값이 최솟값이라면: 현재 배열의 값은 (구간 상 최대점의 $y$ 좌표) $- \sum_{j = 1}^{q} v[j]$ 이다. 최고점에 도달했을 때는 무조건 사탕이 가득 차 있기 있기 때문이다.

이제 전체 문제는 세그먼트 트리를 사용하여 해결할 수 있다. $v[j]$ 의 prefix sum을 값으로 가지는 세그먼트 트리를 만들고, 각 노드에 대해서 구간 최댓값과 최솟값을 관리하자. 먼저, 최고점과 최저점의 높이 차가 $C[i]$ 이하로 유지되는 가장 긴 suffix는 이분 탐색을 통해서 $O(\log^2 N)$ 에 찾거나, 트리를 타고 내려가면서 $O(\log N)$ 에 찾을 수 있다. 이 점을 찾은 후에는, 그냥 이 점과 그 왼쪽을 시작점으로 하는 Suffix의 최댓값 / 최솟값만 구해주면 최종 값을 판별하는 데 필요한 모든 정보를 얻을 수 있다.

갱신된 시점에는, 어떠한 Suffix에 특정한 값을 더한 후 위 두 값을 관리해야 한다. 이는 Lazy propagation을 사용하면 된다. 총 시간 복잡도는 $O((N + Q) \log N)$ 이다.

서브태스크 4 풀이와 Sqrt decomposition

사실 본인은 서브태스크 4의 풀이를 모른다. 들었던 방향성은, 서브태스크 3에서 볼 수 있듯이 $C$ 가 고정되면 쿼리 적용 이후의 함수가 3개 정도의 정수로 표현 가능하며, 여러 개의 $C$ 에 대해서도 이 함수를 스택 등으로 열심히 비비면 잘 구할 수 있다는 내용이었다. 더 자세히 알아보고 싶으면 이런 글을 보면 될 것 같다. 시간 복잡도는 $C$ 의 정렬을 제외하면 $O(N + Q)$ 로 보인다.

확실한 것은, 서브태스크 4를 $O(N + Q)$ 정도에 처리할 수 있으면 전체 문제도 $O((N + Q)\sqrt Q)$ 정도에 처리할 수 있다. 쿼리를 $\sqrt Q$ 조각으로 쪼개서 처리하자. 쿼리가 $\sqrt Q$ 개라면, 전체 배열을 각 구간에 적용되는 쿼리의 집합에 따라서 $2\sqrt Q$ 개의 구간으로 나눌 수 있다. 이 구간 각각을 $O(len + \sqrt Q)$ 에 처리하면, $\sqrt Q$ 개의 쿼리가 $O(N + Q)$ 에 처리된다. 이를 $\sqrt Q$ 번 반복하면 전체 문제가 $O((N + Q) \sqrt Q)$ 시간에 처리된다.

반딧불 학생과 김동현 코치가 이러한 식으로 해결했다고 한다. 다만 Sqrt를 사용하기 때문에 어느 정도 효율적인 구현은 필요해 보인다.

이 아이디어에 멋진 자료구조를 추가하면 $O(Q \log^2 N)$ 에 온라인으로도 풀 수 있는 것 같다.

문제 2. 열쇠

서브태스크 1 (9점)

37점까지는 p[i]의 최소를 구한다 가 아니라 모든 p[i]를 구한다 고 생각해도 문제가 풀린다. 여기서도 이러한 식으로 접근한다.

만약 현재 방에 0번 열쇠가 없다면, 답은 1이다. 그렇지 않다면, 답은 해당 방에서 도달 가능한 방의 개수이다. 이는 DFS로 계산할 수 있다.

서브태스크 2 (20점)

각 $i$ 에 대해서 따로 문제를 해결한다. 매 순간 현재 도달 가능한 정점 집합 $S$ 를 관리하고, $S$ 의 크기를 하나씩 늘리는 것을 시도해 볼 수 있다.

  • 현재 $S$ 에 있는 모든 키의 종류를 배열에 마크한다.
  • $S$ 에 인접하며, $S$ 에 있는 키로 도달 가능한 다른 정점 하나를 골라, $S$에 넣는다. 그러한 정점이 없으면 그대로 종료한다.

이를 반복하면 각 $i$ 에 대해서 문제가 $O(nm)$ 에 해결되며 전체 문제는 $O(n^2m)$ 에 해결된다.

서브태스크 3 (37점)

위 과정을 큐를 사용하여 최적화한다. 너비 우선 탐색을 사용하고, 추가적으로 “현재까지 발견된 키”, “현재까지 발견되지 않은 키로 들어갈 수 있는 정점” 리스트를 관리한다. 새로운 정점을 방문하였을 때, 이 정점에서 새로운 종류의 키를 발견했다고 하자. 그렇다면 지금까지 해당 키가 없어서 들어가지 못했던 정점 리스트를 바로 다 방문할 수 있으니, 전부 큐에 넣어준다. 이 정점에서 인접한 정점을 현재까지 발견한 키로 방문할 수 있다면 큐에 넣어주고, 아니면 나중에 해당 키를 받았을 때 바로 들어갈 수 있도록 리스트에 쌓아둔다.

만점 풀이

서브태스크 4만 푸는 풀이는 잘 모르겠다. 주위에서도 알아낸 사람이 없고, 데이터가 약하다는 제보 정도만 조금 있는 것 같다. 뭐가 됐든 만점 풀이와는 큰 상관이 없지 않나 싶다.

정점 $v$ 에서 $r[v]$ 번 키를 사용하여 다른 정점에 방문할 수 있다면, 이러한 정점 중 하나 (여럿일 경우 아무거나) 를 $w(v)$ 라고 하자. $w(v)$ 가 도달할 수 있는 정점들은 모두 $v$ 에서 도달할 수 있음을 알 수 있다. 다른 말로, $S_{w(v)} \subseteq S_v$ 이다. 만약 그러한 정점이 없다면 $w(v) = v$ 라고 하자.

이제 $v \rightarrow w(v)$ 로 간선을 이어주자. 이러한 그래프의 각 컴포넌트는 사이클 하나를 루트로 한 트리 형태를 한다는 것이 잘 알려져 있다. 각 간선은 집합의 포함 관계를 나타내니, 한 사이클에 묶여있는 정점들은 서로가 서로를 포함하는 관계고 이들 간에는 도달할 수 있는 정점들의 집합이 같다. 고로, 이들을 하나의 정점으로 묶어서 생각할 수 있다. 이 정점들이 가진 키, 그리고 이 정점에서 인접한 다른 정점들을 모두 하나로 합쳐주면, 사이클의 크기가 항상 2 이상이니 정점의 개수가 줄어든다. 이렇게 새롭게 합쳐진 정점에서도 위와 같이 $w(v)$ 를 정의하자. 이 때 키는 하나가 아니고 여러 개라는 것이 차이점이다.

이렇게 줄어든 그래프에서도 문제를 푸는 것을 반복하면, 더 이상 길이 2 이상의 사이클이 생기지 않는 (다른 말로, 사이클에서 도달할 수 있는 새로운 정점이 없는) 시점이 생기게 된다. 이 때, 각 트리의 루트를 제외한 정점들은, 모두 트리의 루트를 방문할 수 있다. 하지만 트리의 루트에서는 자신을 제외한 정점을 방문할 수 없다. 고로, 트리의 루트만이 유일한 답의 후보가 되며, 루트에서 도달할 수 있는 정점의 수는 단순히 해당 정점에 합쳐졌던 초기 정점의 집합이니, 쉽게 계산할 수 있다. 만점 풀이의 아이디어는 이것이 끝이고, 이를 Naive하게 구현하면 $O(nm)$ 정도의 시간이 걸릴 것이다.

이제 이 과정을 최적화하자. 최적화를 할 때는 특별히 문제의 성질에 대해서는 관찰할 필요는 없고, 효율적인 자료구조를 고민하는 것으로 충분하다.

  • 사이클을 찾는 것은 Union-find를 통해서 해 줄 수 있다.

  • 합쳐진 정점을 관리하는 것은 또 다른 Union-find를 통해서 해 줄 수 있다.

  • 두 정점을 합칠 때 키와 인접 리스트를 합쳐줘야 하는데 이는 Small-to-large를 통해서 해 줄 수 있다.

  • 새로운 정점을 만들었을 때 $w(v)$ 를 빠르게 찾아야 한다. 리스트를 관리할 때 인접한 간선들 중 현재 가진 Key들로 도달이 가능한지 아닌지 를 기준으로 집합을 두 조각으로 나누자. 두 집합을 합쳐줄 때, 작은 쪽에서 새롭게 들어온 Key들을 넣으면서 리스트를 조정할 수 있다. 이 부분은 어느 정도 Naive하게 해 줘도 되는 것이, 한 간선은 도달이 불가능한 상태에서 가능한 상태로 바뀌지 그 반대로 되지는 않기 때문이다. 이걸 키 단위로 조금 나이브하게 합쳐주는 것이 67점 풀이일지도 모르겠다.

    아무튼 도달이 가능한지 불가능한지의 여부로 간선 집합을 분리했으니, 집합에서 아무 간선이나 뽑으면 $w(v)$ 를 찾을 수 있다. Self-loop만 아니면 되는데, Self-loop인지는 Union-find로 확인해 보고, 맞으면 지워버리면 된다.

시간 복잡도는 $O(M \log^2 N)$ 이다. 여담으로, 본인은 알고리즘이 Directed MST를 구하는 효율적인 알고리즘과 비슷하다는 느낌을 많이 받았다. 이번 기회에 한번 공부해 보는 것도 좋을 것 같다.

문제 3. 분수 공원

서브태스크 2 (15점)

문제를 크게 두 가지 부분으로 나눌 수 있다.

  • 공원의 분수를 잇는 스패닝 트리가 있는지 찾고, 있다면 만드는 것
  • 스패닝 트리의 각 도로에 대해 서로 다른 벤치를 매칭할 수 있는지 찾는 것

(이 글에서는 스패닝 트리의 간선을 “도로” 라고 부른다. 간선에 간선을 매칭한다 같은 혼란스러운 표현을 막기 위해서이다.)

스패닝 트리를 만드는 방법이 여러 가지가 있고, 이 중 어떤 방법을 택하는지에 따라서 두 번째 부분이 어려워 질 수 있다. 일단은, 아무 스패닝 트리나 잡아도 매칭을 할 수 있다고 믿음을 가진 후 문제를 해결해 보자.

아무 스패닝 트리나 찾는 방법은 다음과 같다. 전체 점을 $(x, y)$ 좌표 순서로 정렬한 후, 정렬 순서상에서 인접한 두 점의 거리가 2인 경우 도로를 이어준다. 반대로 $(y, x)$ 좌표 순서로 정렬한 후 똑같이 해 주면, 모든 가능한 도로의 후보가 나온다. 이제 이 그래프에서 Union-find 등으로 아무 스패닝 트리나 찾아주면 된다. 만약 그래프가 연결이 아니라면 여기서 -1을 반환하면 된다.

스패닝 트리의 각 도로에 벤치를 매칭하는 방법을 살펴보자. 이 서브태스크에서는 상당히 간단한 방법으로 벤치를 매칭할 수 있다. 벤치의 가능한 위치를 $x = 1, x = 3, x = 5$ 로 나눈 후, $x = 1$ 은 왼쪽 세로 도로, $x = 3$ 은 가로 도로, $x = 5$ 는 오른쪽 세로 도로에 매칭할 것이다. 왼쪽 세로 도로는 중점에서 왼쪽으로 한 칸 움직인 위치에 벤치를 두고, 오른쪽 세로 도로는 중점에서 오른쪽으로 한 칸 움직인 위치에 벤치를 두고, 가로 도로는 중점에서 위로 한 칸 움직인 위치에 벤치를 두자. 이 방법을 사용하면, 아무 스패닝 트리를 찾아도 항상 벤치를 매칭시켜줄 수 있다.

서브태스크 4 (35점)

서브태스크 4에서는 가능한 스패닝 트리가 유일하다. 스패닝 트리는 대충 찾고, 벤치 매칭만 최적으로 신경써서 해 주면 된다.

스패닝 트리를 구하고, 각 도로에 인접한 벤치들을 모두 구해주자. 각 도로에 대해서 정확히 두 개의 벤치와 매칭을 해 줄 수 있을 때, 모든 도로를 벤치와 매칭하는 문제가 된다.

이는 전형적인 이분 매칭으로, $O(N^2)$ 시간에 문제를 해결할 수 있다. 하지만 이는 비효율적이다. 효율적으로 문제를 해결하기 위해서는 각 도로가 정확히 두 개의 벤치 와 매칭된다는 사실을 활용해야 한다. 벤치를 정점으로 하고, 각 도로가 매칭되는 두 벤치 사이에 간선을 잇자. 우리가 해결해야 하는 문제는, 이 그래프의 각 간선에 서로 다른 정점을 매칭해 주는 문제이다. 이 문제는 선형시간에 해결할 수 있는데,

  • $V < E$ 인 컴포넌트가 있으면 매칭이 불가능하다.
  • $V - 1 = E$ 인 경우는 그래프가 트리이다. 아무 정점을 루트로 잡자. 모든 간선에 대해서, 루트에서 멀어지는 쪽의 정점을 매칭한다. 이 경우 모든 간선이 서로 다른 정점에 매칭되며 루트는 매칭되지 않는다.
  • $V = E$ 인 경우 그래프에 사이클이 정확히 하나 존재한다. 사이클 상의 아무 간선을 잡은 후, 양 정점 중 아무 곳에나 매칭한다. 매칭한 간선을 지우고, 매칭에 들어있는 정점을 루트로 한 트리에서 위 알고리즘을 활용하여 매칭을 구해준다.

서브태스크 3/5 (70점)

서브태스크 4를 구현하면 70점까지 받는 것은 어렵지 않다. 아마 35점을 받을 의도로 구현했다 하더라도 55점 / 70점을 받았을 가능성이 높다. 풀이를 살펴보자.

  • 서브태스크 5의 경우, 스패닝 트리를 어떻게 구해도 각 벤치에 인접한 도로가 최대 2개이다. 위에서 매칭을 구한 그래프로 생각하면, 모든 정점의 차수가 최대 2라는 것이다. 이 경우 그래프의 각 연결 컴포넌트는 트리 혹은 사이클이라서, $V \geq E$ 가 항상 만족하고, 매칭이 항상 존재한다.
  • 서브태스크 3의 경우는 웬만한 스패닝 트리가 반례가 되지 않는다. 예를 들어, 세로 선분을 우선으로 하고, 남으면 아래에 있는 가로 선분부터 넣는 식으로 스패닝 트리를 구성하자. 이렇게 구현할 경우 AC가 나오고, 반례도 제한 안에서는 없는 것으로 보인다. 좋은 풀이는 아니지만, 굳이 엄밀히 따질 것 까지는 없어 보인다.

서브태스크 5의 간단한(?) 풀이 (55점)

만점 풀이를 소개하기 앞서, 서브태스크 5를 풀 수 있는 다른 풀이를 소개한다. 이 풀이는 서브태스크 5의 성질을 조금 더 자연스럽게 사용하며, 매칭을 따로 구해줄 필요가 없다. 사실 그렇게 간단한 풀이인지는 모르겠지만, 이 풀이를 이해해야 만점 풀이로 넘어갈 수 있다.

벤치를 중심으로 하는 2x2 정사각형 하나를 셀 이라고 부르자. 문제에서 주어진 평면을 셀 로 분할할 수 있으며. 도로는 셀과 셀 사이의 경계를 보여준다.

모든 셀 을 Chessboard와 같이 흑백으로 칠한다. 이 중 검은 셀은 가로 도로 를 담당하고, 하얀 셀은 세로 도로 를 담당한다. 서브태스크 5에서는, 각 벤치에 인접한 가로 도로가 최대 하나고, 세로 도로도 최대 하나이다. 검은 셀에 가로 도로가 인접하다면 둘을 매칭하고, 하얀 셀에 세로 도로가 인접하다면 둘을 매칭하자. 모든 가로/세로 도로에 대해서, 인접한 검은/하얀 셀이 무조건 존재하니, 이렇게 매칭하면 모든 도로를 셀에 매칭할 수 있다. 이렇게 하면 스패닝 트리를 구할 필요도 없고, 매칭도 구할 필요도 없이, 바로 문제가 해결된다.

만점 풀이

위와 같이 모든 셀을 흑백으로 칠하는데, 이번에는 검은 셀에 가로 도로가 2개 인접할 수도 있고, 하얀 셀에 세로 도로가 2개 인접할 수도 있다. 각 셀에서 둘 중 적절한 도로를 하나 골라서, 그래프가 여전히 연결되게끔 구성해야 한다.

다음과 같은 알고리즘을 생각하자:

  • 검은 셀에 가로 도로가 2개 인접하면 상단 가로 도로를 고른다. 1개 인접하면 상하 상관없이 그 하나를 고른다.
  • 하얀 셀에 세로 도로가 2개 인접하면 좌측 세로 도로를 고른다. 1개 인접하면 좌우 상관없이 그 하나를 고른다.

이후 선택된 도로들을 반환한다. 이게 풀이의 끝이고, 이를 구현하면 만점을 받는다.

이제 알고리즘을 증명하자. 이 알고리즘에서 각 셀은 항상 서로 다른 도로를 고르게 된다. 고로 선택된 도로들이 연결되었음만 증명하면 된다. 들어가기 앞서, 분수들이 5x5 그리드일때 어떠한 도로들이 선택되는 지를 그림으로 살펴보자.

Image from iOS

이제 알고리즘을 증명한다.

정점을 셀 + 외곽의 무한한 면 (Outer face) 으로 하고, 인접한 두 셀이 고르지 않은 도로로 분리되어 있으면 간선을 그어주자. 이 그래프에 단순 사이클이 있으면, 전체 그래프가 연결되어 있고, 없으면, 그래프가 연결되어 있지 않다. (이는 Dual Graph의 성질로, Cut-Cycle Duality라고 부른다). 이 사이클이 Outer face를 포함한다고 하고 (그렇지 않은 경우도 동일하다), 사이클에 속한 간선을 ${e_1, e_2, \ldots, e_k}$ 라고 하자.

일반성을 잃지 않고 $e_1$ 이 가로 간선이며, 또 사이클이 아래에서 위로 올라오는 방향으로 형성되어 있다고 하자, 이 경우, $e_1$의 아래는 하얀 셀, 위는 검은 셀이어야 한다. 위가 검은 셀인데 아래가 뚫렸다는 것은, 이 셀의 모서리에 모두 분수가 있다는 뜻이다. 고로 위쪽/오른쪽 길이 막혀 있으며, 왼쪽으로 움직여야 한다. 왼쪽이 하얀 셀인데 오른쪽이 뚫렸다는 것은, 이 셀의 모서리에 모두 분수가 있다는 뜻이도다. 고로 아래/왼쪽 길이 막혀 있으며, 위로 움직여야 한다. 이 논리를 무한히 반복하면, 분수의 개수가 유한하다는 가정에 모순이다.

그림으로 그리면 대충 이렇다.

Image from iOS (1)

요약하자면, 저렇게 대각선으로 체인이 날아가는 트리를 그려주어서 항상 매칭이 존재하는 그래프를 만들 수 있다. 이렇게 보면 결론은 참 간단하지만, 풀기는 상당히 어려운 문제라고 생각한다.

문제 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$ (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로 충분하다.