솔브드 아레나 파티 미러 (solved.ac Arena #19, Div.1) 참가 후기

2월 3일에 열린 솔브드 아레나 파티 Div.1에 미러로 참가했다. 대회 장소가 집에서 멀기도 하고 아레나 #10~#16에 전혀 참가하지 않아서(Arena #16 운영 제외) 선정될 확률도 없었던 터라 본 대회에 참가 신청을 하진 않았다.

 

대회 결과 5솔브로 본 대회+미러 합산 8등을 했다. 막판에 H를 풀었다면 등수가 크게 올랐을 것 같아서 아쉽다.

A. 정렬된 연속한 부분수열의 개수 (0:02)

문제의 조건을 만족하는 모든 $(i, j)$에 대해, $[i, j]$가 다음 조건을 만족하는 $[l, r]$ 중 정확히 하나의 부분구간임을 보일 수 있다.

• $A_l < A_{l+1} < \cdots < A_r$
• $l=1$이거나 $A_{l-1} > A_l$
• $r=N$이거나 $A_r > A_{r+1}$

다르게 말하면, 문제의 조건을 만족하는 모든 $(i, j)$는 더 이상 연장할 수 없는 오름차순 부분구간 중 정확히 하나에 속한다. 또한, 이렇게 더 이상 연장할 수 없는 오름차순 부분구간 내에 있는 모든 구간이 문제의 답이 된다.

 

따라서 문제를 푸는 과정은 크게 두 가지로 나뉜다. 1) 먼저 주어진 수열을 오름차순 구간으로 분할한다. 이것은 단순히 $A_i > A_{i+1}$인 곳에서만 분리를 해 주면 되기 때문에 쉽다. 2) 앞에서 구한 오름차순 구간들에 대해, 각각의 부분구간의 개수를 모두 더한다. 길이 $len$인 구간의 부분구간 수는 ${}_{len} H_2 = \frac{len(len+1)}{2}$라는 점을 이용하면 좋다.

 

위와 같이 문제를 쉽게 풀 수 있고, 시간 복잡도는 $\mathcal{O}(N)$이다.

B. 과부하 방지 (0:15)

먼저 답에 대한 이분 탐색을 사용할 것이다. 따라서, 우리는 답이 $V$ 이상이 될 수 있는지만 판단하면 된다. 문제 조건상 $V$개의 장치들이 전기를 공급받을 수 있을 때, $V-1$개의 장치들이 공급받을 수 있음이 자명하므로 이분 탐색을 사용할 수 있는 것이다.

 

만약 수 $V$가 정해졌다면, 어떤 장치들을 이용하는 것이 가장 효과적일까? $D_i$는 작을수록 더 엄격한 제한 조건이므로, 당연히 가장 큰 $D_i$들을 골라야 할 것이다. 따라서, 우리는 가장 큰 $D_i$의 값 $V$개에 대해 문제 조건을 만족시킬 수 있는지를 보면 된다. 편의상, 소켓 수가 $1$인 멀티탭은 오히려 악영향만 주므로, 이러한 멀티탭이 없다고 가정하자. (만약 있다면, 단순히 무시하면 된다.)

 

문제의 상황을 트리와 같이 생각할 수 있다. 꼭 이래야 하는 것은 아니지만, 이렇게 했을 때 논의하기 편한 구석이 있다. 일단 루트 정점이 하나 있다고 가정하고, 맨 처음에 주어지는 $K$개의 벽 콘센트를 루트 노드의 자식이라고 생각한다. 또한 콘센트를 하나 꽂을 때마다 새로운 소켓이 생기는데, 이들을 각각 이 콘센트를 꽂은 소켓 노드에 대한 자식 노드라고 생각하자. 그럼 다음과 같은 식으로 문제를 변형해서 생각할 수 있을 것이다.

• 깊이 $0$인 노드 $K$개가 주어진다. (논의의 편의상 루트의 깊이를 $-1$이라고 생각하자. 또는 애초에 문제 상황을 트리 $K$개의 포레스트라고 가정해도 문제가 없다.)
• 각각의 노드에 대해, 다음 세 가지 선택지 중 하나를 택한다.
  • 해당 노드에 $i$번 전자기기를 꽂는다. 이때, 이 노드의 깊이는 $D_i$ 이하여야 한다.
  • 해당 노드에 소켓이 $A_i$개인 멀티탭을 꽂는다. 이렇게 하면 이 노드를 부모로 갖는 자식 노드 $A_i$개가 추가로 생긴다.
  • 해당 노드를 무시한다.
• 모든 전자기기에 노드를 배정할 수 있는지 판별하여라.

이제 이 문제를 해결하기 위한 그리디한 전략을 제시한다. 먼저, 트리의 구조 전부가 중요한 것이 아니라는 점을 관찰하자. 실제로 중요한 것은 깊이 $i$에 몇 개의 노드가 있는가 하는 사실뿐이다. 따라서, 트리 전체를 관리할 필요 없이 현재 깊이의 노드 수만 관리하면 된다. 처음에는 깊이 $0$의 노드 $K$개로 시작한다. 이후 아래 전략에 따른다. 현재 깊이를 $d$라고 하자.

• 먼저 $D_i = d$인 전자기기가 남아 있다면 그들을 지금 모두 배정한다. 만약 현재 깊이의 소켓 수가 부족하다면 답은 불가능이 된다.
• 위 과정을 거치고 남은 소켓이 있다면, 모두 멀티탭을 연결한다. 남은 멀티탭이 여러 개라면, 그들 중 가장 소켓 수가 많은 것을 먼저 연결한다. (소켓 수가 많은 멀티탭은 먼저 사용하는 것이 당연히 이득이다. 문제 상황상 너무 당연하므로 증명을 생략한다.)
• 위 과정까지 거쳤는데도 현재 깊이에 남은 소켓이 있다면, 남은 전자기기 중 $D_i$ 값이 가장 작은 전자기기들부터 순서대로 배정한다.

위 그리디 전략에 대한 증명은 따로 하지 않는다. 사전에 $A$와 $D$를 모두 적당한 순서로 정렬해 두면 위 과정은 $\mathcal{O}(N)$에 가능하다. 따라서, 전체 문제를 $\mathcal{O}(N \log N)$에 해결할 수 있다.

D. 가스 충전소 (1:11)

원래는 C를 먼저 풀 예정이었으나, 후술할 이유로 몇십 분을 날리다 사람들이 더 많이 푼 D로 갔다. 그리고 2022 선발고사 날다람쥐와 사실상 똑같은 문제라서 쉽게 풀었다.

 

이 문제에서 가장 중요한 아이디어는 다음과 같다.

• 결국 문제는 $i$번 주유소에서 $i+1$번 주유소까지 갈 동안 어떤 주유소의 기름을 얼마나 이용하는지, 그 조합을 정하는 문제로 환원할 수 있다.
• 실제로 $i$번 주유소에서 $i+1$번 주유소로 가는 동안, 위에서 언급한 기름 말고 차후를 위한 기름도 가지고 다녔을 것이다. 그러나, 이런 기름에 대해서는 나중에 생각해도 늦지 않다. 일단 지금 당장 급한 기름에 대해서만 확정해도 충분하다.
  • 위 설명이 조금 애매한 감이 있다. solved.ac 난이도 기여를 보다 더 직관적인 dk10211님의 설명을 찾았다. 그분의 설명에 의하면, 일단 앞서 기름을 구매했다고 가정하고, 나중에 더 좋은 선택지가 나온다면, 해당 기름을 버린다고 간주하는 것이다. 사실 정확히는 버린다기보다는 애초에 구매한 적이 없었다고 생각하는 것에 가깝다.

위 아이디어가 무슨 뜻인지 자세히 알아보기 위해 풀이를 설명하겠다. 구현에 대한 디테일을 생략하고 설명하면 다음과 같다. 아래 설명에서도 보듯이, 기름을 연속적인 유체로 생각하지 않고, 기름 $1$리터를 하나의 덩어리같이 생각하는 것이 편리하다.

• 풀이의 전 과정에서, 현재 구매 가능한 기름 가격의 선택지를 담은 배열 $P$를 관리할 것이다. 이때 구매라는 단어에 조금 애매함이 있다. 이 풀이에서는, 기름의 구매 시점을 주유소를 지날 때가 아닌 실제로 그 기름을 사용하는 시점으로 생각한다.
  • 이렇게 문제를 변형하면, 자동차가 운행하는 어느 시점에 연료 용량인 $F$ 리터를 넘으면 안된다는 조건을 어떻게 처리하는가? 단순하다. 배열 $P$의 크기를 $F$ 이하로 관리하는 것이다. 자세한 과정은 아래에서 보자.
• 하나의 주유소를 지나는 순간, 배열 $P$에는 정수 $p_i$가 $a_i$개만큼 삽입된다.
• 그 이후, 배열 $P$의 크기를 $F$ 이하로 관리하는 것이다. 가능한 옵션이 여러 가지 있다면, 당연히 가장 비싼 옵션을 삭제하는 것이 이득이므로, $P$에서 가장 큰 원소를 빼는 작업을 크기가 $F$가 될 때까지 반복하면 된다.
• 이후 $1$ 킬로미터를 주행할 때에는, 배열 $P$에서 가장 작은 원소를 뽑고, 해당 기름을 구매한다. 사실 도로 주행 중에 기름을 구매할 수는 없기 때문에 이 기름을 예전에 구매했다고 가정한다는 것이 더 옳은 표현이다.

실제로 $F$가 매우 크므로 배열 $P$를 관리할 수는 없다. 이를 구현하는 방법은, 배열 $P$에 겹치는 값이 많다는 점을 이용하는 것이다. $P$를 std::map으로 관리하고, $map[x]$를 현재 $P$에 있는 $x$의 개수와 같은 느낌으로 관리하면 문제를 $\mathcal{O}(N \log N)$에 해결할 수 있다.

E. 아리스, 청소합니다! (2:13)

풀이는 제법 빨리 나왔는데, 이 풀이가 실제로 시간 제한 안에 통과할지를 못 믿어서 오랫동안 구현을 안 했던 문제이다. 개인적으로 이렇게 풀이를 찾아놓고도 시간제한에 대해 고민하게 만드는 문제를 좋아하진 않는다. (상수 차이로 고민하는 경우만을 말한다. 독특한 방식으로 시간 복잡도 자체가 감소함을 증명하는 문제에 대해 말하는 것은 아니다.) 어쩌면 다양한 알고리즘의 상수 차이에 대한 경험 부족일 수도 있다.

 

이런 점을 신경쓰지 않는다면, 문제 풀이 자체는 굉장히 straightforward하다. 아리스의 상태를 현재 위치와 방향의 순서쌍으로 정의하자. 한 상태가 여러 번 방문되면, 먼지가 존재하는 상태는 많아야 최초 한 번뿐이고, 나머지는 모두 먼지가 존재하지 않는 상태임을 관찰할 수 있다. 따라서, 이미 한 번 먼지가 사라졌다면, 다시 먼지가 있는 칸을 방문하기 전까지는 똑같은 상태들로 이루어진 경로를 거칠 것임을 예측할 수 있다. 이런 상태들끼리 연결하면 방향 그래프를 만드는 것이 가능하다.

 

먼지가 없는 상태에서의 이동을 표현한 방향 그래프 $G$를 생각하자. (방향 그래프 $G$는, 당연하게도, 규칙표 $B$를 이용해 만들 수 있다.) 어떻게 보면, $G$는 functional graph의 조건을 만족하고, 이렇게 부르는 편이 더 적절해 보인다. 이 문제를 해결하는 방법은 다음과 같다.

• 먼저 $G$의 edge를 모두 찾는다. 즉, 모든 상태에 대해, 해당 칸에 먼지가 없을 때 다음으로 도착하는 칸의 번호를 구한다.
• 이후 아리스의 초기 상태에서 시작해 다음을 반복한다.
  • 만약 현재 칸에 먼지가 있다면, 먼지를 제거한다. 그 뒤 주변 $4$개의 칸을 보며, 해당 칸에서 현재 칸으로 올 수 있는 상태에 대해, 이에 대응되는 $G$의 간선을 찾고 Union Find에서 해당 두 정점을 연결한다. 이때, 현재 아리스가 위치해 있는, 먼지를 방금 제거한 칸이 루트가 되도록 한다. 이때, 만약 두 상태가 이미 Union Find에서 같은 연결성분 안에 있다면, 사이클이 생겼다는 뜻이므로 즉시 종료한다.
  • 만약 현재 칸에 먼지가 없다면, 중간 과정을 생략하고 바로 다음에 만날 먼지가 있는 칸으로 이동할 수 있다. Union Find에서 현재 상태가 속한 트리의 루트 정점으로 이동하면 된다. 이때, 만약 직사각형 격자 밖으로 이동한다면, 마지막으로 먼지를 제거한 시점을 출력하면 된다.

시간 복잡도가 $\mathcal{O}(HW \log {HW})$이다. 제한이 워낙 크고, 상태가 칸마다 4개라서 상수도 조금 큰 덕에 당연히 TLE가 날 거라고 예상했으나, Union Find의 상수 자체가 워낙 작은 덕에 통과하는 것 같다.

C. 반 나누기 (2:41)

문제 자체는 어디서 본 적이 있는 것 같이 생겼다. 실제로 대회가 끝나고 notorious coincidence가 발견되었다고 들었다.

 

문제 풀이는 단순하다. 주어진 다각형에서 투 포인터 알고리즘을 이용할 것이다. 다각형의 둘레를 구한 다음, 포인터 $A$는 $1$번 정점에, 포인터 $B$는 둘레가 정확히 반이 되는 지점에 놓고, 두 포인터 사이 둘레가 항상 절반으로 나뉘도록 투 포인터 알고리즘을 돌리자. 이때, 포인터 $A$와 $B$ 중 어느 쪽이 먼저 다음 꼭짓점에 도달하는지를 판별하고, 그 한계 사이의 구간에 대해 탐색한다. 첫 번째 포인터는 이 간격 동안 선분 $A_l$과 $A_r$ 사이에 위치할 수 있고, 두 번째 포인터는 선분 $B_l$과 $B_r$ 사이에 위치할 수 있다.

 

만약 다각형을 선분 $A_l B_l$이나 선분 $A_r B_r$로 나눴을 때 넓이가 양분된다면 답이 나온 것이다. 그렇지 않다면, $A_l B_l$로 나눴을 때 넓이 차이의 부호(왼쪽 넓이에서 오른쪽 넓이를 뺐을 때의 부호, 즉, 왼쪽 넓이가 더 크면 +, 오른쪽 넓이가 더 작으면 -)와 $A_r B_r$로 나눴을 때의 부호가 다른지 살펴보자. 만약 부호가 다르다면, $A_l$을 $A_r$로 옮기고 $B_l$을 $B_r$로 옮기는 시점에서 양쪽 넓이는 모두 연속적으로 변하므로 중간값 정리에 의해 두 넓이가 같아지는 지점이 적어도 하나 있다. 이 지점을 이분 탐색으로 찾으면 문제가 해결된다.

 

이 문제에서 가장 중요한 논증은 $A_l B_l$과 $A_r B_r$의 넓이 부호가 다른 시점이 항상 존재한다는 것을 보이는 것이다. 이 사실은 다음과 같이 설명할 수 있다. $A$와 $B$를 계속 돌리다 보면, 어느 시점에서 $A$는 $B$가 되고, $B$는 $A$가 된다. 그런데 이 시점에서 $AB$로 다각형을 잘랐을 때, 왼쪽 다각형과 오른쪽 다각형의 넓이 차는 처음과 절댓값은 같고 부호만 다르다. 왼쪽과 오른쪽 다각형이 뒤바뀌었기 때문이다. 따라서 아까의 연속과 중간값 논리를 쓰면, 연속함수 $f(x)$가 $f(x) > 0$인 $x$와 $f(x) < 0$인 $x$가 모두 존재하므로, $f(x) = 0$인 $x=0$이 존재할 수밖에 없는 것이다. 이렇게 문제를 $\mathcal{O}(N \log N)$에 해결할 수 있다.

 

이 문제에서 나는 1시간 이상을 버렸는데, 결정적인 이유는 실수 오차 때문이었다. 실수 오차가 가장 발생하기 쉬운 부분은 투 포인터로 꼭짓점을 옮기는 부분이다. 이 부분에서 나는 처음에 양쪽 변의 길이를 나눈 뒤 그만큼 포인터를 이동시키는 방식으로 코드를 짰는데, 이러다 보니 실수 오차가 점점 누적되어서 문제가 생겼던 것이다. 실수 오차를 줄이려면 상대적 변화에 의존해 포인터를 이동시키지 말고 그때 그때 절대적인 둘레를 기준으로 계산해야만 한다. 즉, 둘레 값을 기준으로, 포인터 $A$와 그 직전 꼭짓점의 거리가 얼마여야 하는지를 계산하고, 해당 변의 길이로 나눈 뒤 그 비율만큼의 내분점을 잡아야 한다는 것이다.

H. 트리 탐색기 (Upsolved)

풀이는 대회 시간 중에 찾았지만 구현 시간이 부족해서 짜지 못했다. C를 조금 더 일찍 해결했다면 풀 수 있었을 것 같아 아쉽다.

 

문제 풀이 자체는 전형적인 알고리즘의 활용이지만 꽤나 재미있다고 생각한다. 먼저 문제 상황을 트리로 해석한 뒤, Euler Tour Trick (dfs ordering)을 이용해 각 서브트리의 시작 인덱스와 끝 인덱스 $in[x]$, $out[x]$를 모두 구해 놓자. 또한 $in[idx[x]] = x$인 배열 $idx$를 만들자.

 

편의상 초기 상태에서 모든 폴더가 펼쳐져 있다고 가정하자. 이 상태를 배열 $S = [0, 0, \cdots, 0]$인 상태로 생각할 것이다. 이후, 폴더 $x$가 닫히는 변화를 배열의 $S[in[x]+1], \cdots, S[out[x]]$에 $1$을 더하는 것으로 생각하고, 폴더 $x$가 펼쳐지는 변화를 배열의 $S[in[x]+1], \cdots, S[out[x]]$에 $1$을 빼는 것으로 생각하자. 특정 시점에 폴더 $x$ ($x \ge 2$)가 화면에 나타나는지는, $S[x] = 0$인지를 묻는 것과 같다. 이러한 종류의 쿼리를 처리할 수 있는 세그먼트 트리는 흔히 화성 지도 Segment Tree라고 알려져 있는 것과 같고, 이 세그먼트 트리에서 이분탐색을 구현하면 문제를 풀 수 있다. 시간 복잡도는 $\mathcal{O}(Q \log N)$이다.

F. 헤네시스 오솔길 (Upsolved)

대회 중에 오랫동안 안 풀리길래 딱히 깊이 생각해 보지 않은 문제였다. 그러나 대회 종료 후 난이도가 낮게 찍혔고, 실제로 푸는 것도 어렵지 않았다.

 

일단 이런 식으로 주황 버섯이든 개미든 부딪히는 문제는 다음과 같은 관찰을 하는 게 유용하다.

• 버섯이 부딪혀서 서로 방향을 바꾸는 것을 무시해도 전체 $x$좌표 집합은 변함이 없다. 예를 들어, 한 버섯이 $1$번 칸에서 $2$번 칸으로, 한 버섯이 $3$번 칸에서 $2$번 칸으로 이동하며 서로 부딪혔다고 하자. 첫 번째 버섯은 다시 $1$번 칸으로, 두 번째 버섯은 다시 $3$번 칸으로 돌아간다. 하지만 두 버섯이 부딪히는 걸 무시한다고 해도, 버섯 중 하나는 $1$번 칸으로, 하나는 $3$번 칸으로 이동하는 것은 같다. 변화하는 것은 어떤 버섯이 왼쪽으로 갔냐는 사실뿐이다. 따라서, 버섯들이 필드를 빠져나가는 시점을 (순서 없이) 구하는 것이 목적이라면 버섯의 부딪힘을 무시하고 이런 식으로 생각하는 것이 효과적이다.
• 그렇다면 버섯들이 특정 위치에 닿는 시점 리스트를 알았을 때, 실제로 해당 위치에 해당 시점에 닿은 버섯이 어떤 버섯인지는 어떻게 알아낼 수 있을 것인가? 이것은 모든 버섯들의 상대적 위치 순서가 절대 변하지 않는다는 사실에서 얻을 수 있다. 예를 들어, 가장 먼저 왼쪽으로 빠져나간 버섯의 번호가 무엇인가? 당연히 처음에 맨 왼쪽에 있던 버섯일 것이다. 그 어떤 버섯도 해당 버섯보다 왼쪽에 위치할 수 없기 때문이다.

그렇다면, 버섯들의 번호를 무시했을 때, 버섯들은 같은 위치에 놓여도 상관없이 그저 한 방향으로만 이동한다고 생각할 수 있다. 단지 머쉬맘이 명령할 때만 방향을 바꾼다고 생각할 수 있다. 일단 이렇게 문제를 바꿔 놓고, 실제로 머쉬맘이 명령해야 하는 시점의 실제 해를 찾는 것은 나중에 생각하자.

 

나는 다음과 같은 풀이를 통해 AC를 받았다.

• 왼쪽으로 향하는 버섯들의 위치를 관리하는 set과, 오른쪽으로 향하는 버섯들의 위치를 관리하는 set을 만든다.
  • 이때, invert 연산을, 왼쪽으로 향하는 버섯들의 set의 크기보다 오른쪽으로 향하는 버섯들의 set의 크기가 더 클 때, 양쪽 set을 교환하는 연산이라고 정의하자. 이는 머쉬맘이 명령을 내리는 것과 같다.
• 맨 처음에, invert 연산을 시행한다.
• 이후 다음 과정을 set에 버섯이 남아 있을 때까지 반복한다.
  • 어느 쪽에서 먼저 필드를 벗어나는 버섯이 나오는지를 판별하고, 그때까지 걸리는 시간을 계산한다.
  • 빠져나가는 버섯을 set에서 빼 주고, set에 남아 있는 모든 원소들의 위치를 갱신한다.
  • invert 연산을 시행한다.

구현의 디테일을 위해서는, 네 변수를 이용하면 편하다. outL, outR은 현재까지 왼쪽/오른쪽으로 필드를 벗어난 버섯의 수이고, offL과 offR은 set을 실시간으로 갱신할 수 없지만, 한번 업데이트할 때 모든 값에 똑같은 위치 차이만큼 더하거나 빼는 것을 이용해, 초기 위치 대비 변위(?) 같은 값을 저장한 변수이다. offL과 offR을 사용해 필드를 벗어나는 시점을 계산하고, outL과 outR, 그리고 적당한 전처리를 통해 현재 벗어나는 버섯의 번호를 알아낼 수 있다. 이 전체 풀이는 $\mathcal{O}(N \log N)$에 수행할 수 있다.

 

위 그리디 알고리즘이 왜 통하는지 증명하진 않았다. 엄밀한 증명을 원하면 에디토리얼을 보면 될 것 같다. (그런데 에디토리얼은 이것보다 더 간단한 풀이를 쓰는 것 같았다. 뭔가 신기해 보이는데, 가장 중요한 부분의 증명이 자세히 써 있지 않아 잘 이해하진 못했다.)

G. 집합 식 트랜스파일 (Upsolved)

대회 중에는 한 번 쳐다보고 대회 중에 생각할 문제가 아닌 것 같아서 바로 버렸다.

 

일단 길이 제한에 대해 생각하지 말고, 변환이 가능할 조건에 대해 생각해 보자. 이런 류의 문제는 보통 변환이 가능한 경우에는 무조건 문제의 길이 제한도 만족하도록 변환이 되는 경우가 많다. 최소 길이까지 따져가며 변환에 대해 분석하는 것은 매우 어렵고 불가능한 경우가 많기 때문이다. 이 문제에서는 ~ 연산자가 \ 연산자로 바뀌었다. 변환 가능 조건은 매우 단순하고 직관적인데, 모든 집합에 속하지 않는 원소가 들어가지 않으면 된다. 그 경우가 아닌 최대 $2^{20} - 1$개의 나머지 경우는 모두 자명히 A, …, T까지의 집합의 교집합, 합집합, 차집합으로 나타낼 수 있기 때문이다.

 

그렇다면 조건을 만족하는 경우, 식의 길이가 짧도록 변형하는 방법이 무엇일까? 일단 처음 식의 길이를 $L$이라고 할 때, $L$에 등장하는 집합의 개수 $N$이 최대 $\lceil \frac{L}{2} \rceil$임을 알 수 있다. 즉, $L \ge 2N-1$이 성립한다.

 

각각의 집합 문자들 중 ~가 들어간 횟수의 홀짝성을 그 문자의 기우성이라고 하자. 예를 들어 (A|B)&~C에서 첫 번째 집합 문자인 A와 두 번째 집합 문자인 B의 기우성은 짝수이고, C의 기우성은 홀수이다.

 

이 사실을 알고 있는 채로, 문제를 재귀적으로 푸는 solution을 만들 수 있다. 일단 주어진 문자열을 파싱해 &와 | 주변에 항상 괄호를 넣어 주자. 이는 스택으로 할 수 있다. 이렇게 하면 문자열을 이진 트리처럼 해독하는 게 가능하다. 이때 각 자손은 ~가 붙어 있거나 안 붙어 있을 수 있다. 이제 트리 위에서 DFS를 하면서 다음 케이스워크를 하자.

• 만약 현재 노드의 형태가 A&B 또는 A|B라면 그대로 유지한다.
• 만약 현재 노드의 형태가 ~A&~B 또는 ~A|~B라면 각각 ~(A|B)와 ~(A&B)로 바꾼다.
• 만약 현재 노드의 형태가 ~A&B 또는 A&~B라면 각각 B\A와 A\B로 바꾼다.
• 만약 현재 노드의 형태가 ~A|B 또는 A|~B라면 각각 ~(A\B)와 ~(B\A)로 바꾼다.

위 과정을 통해 ~가 문자열의 맨 앞에만 나오도록 할 수 있다. 이때 맨 앞에 ~가 있다면, 모든 집합에 속하지 않는 원소가 답에 들어간다는 뜻이다. (증명은 위 process에서 귀납적으로 하면 된다.) 따라서 이런 경우 불가능으로 판정해 주면 된다.

 

문제가 되는 것은 괄호의 개수인데, 괄호를 잔뜩 추가해 주었기 때문에 길이가 지나치게 길어질 것 같다. 그러나 앞에서 $L \ge 2N-1$임을 보였고, 현재 식의 길이는 집합 $N$개, 연산자 $N-1$개, 그리고 괄호 $2N-2$개라 총 $4N-3$으로 $4N$ 이하임을 알 수 있다.

 

식의 길이가 $2024$ 이하이기 때문에 이 문제를 풀기가 많이 편하다. 파싱을 제곱에 해도 된다. 위 재귀 케이스 처리를 할 떄 $A$와 $B$ 위치 교환을 할 일이 생길 수 있는데, 그것도 나이브하게 해도 된다. $\mathcal{O}(N)$에 푸는 것이 가능해 보이지만(여기서 보이지만인 이유는 깊게 생각을 안 해봤기 때문이다), 편하게 $\mathcal{O}(N^2)$에 풀어도 된다. 사실 원래 문제 자체가 파싱 문제라 구현이 매우 복잡할 수밖에 없는데, 출제자의 배려가 돋보이는 부분이다. (사실 스페셜 저지 때문은 아니었을까?)

총평

문제들은 그 자체로만 보면 퀄리티가 꽤 좋았다고 할 수 있고, 실제로 대회 중에도 꽤 재미를 느꼈다. 하지만 몇몇 문제는 대회에서 풀기는 조금 싫은 유형이라고 생각이 들긴 했다. 예를 들어 C번 (실수 오차 문제가 생길 수 있는 기하), G번 (연산자 우선순위 파싱)은 문제 자체의 질이 좋더라도 조금 꺼려지는 유형이긴 하다. (일단 풀이를 찾아야 문제 질을 평가하는데 풀기가 싫으니까…) E번도 문제 자체는 괜찮았으나 살짝 믿고 제출하는 느낌이 있었다. 비록 TL이 넉넉하긴 해도 조금 더 늘려 놓았으면 좋았을 것 같다. (2~3초로 늘려도 다른 뚫는 풀이가 뚫긴 힘들어 보인다.)

 

전반적으로 만족스러운 대회였다. 내년에 비슷한 행사가 열린다면 가 보는 것도 좋을 것 같다. 그리고 이런 큰 대회 많이많이 열어줬으면 좋겠다.

 

p.s. 한 반절까지 썼을 때 후기 이벤트 공지가 떴다. 이렇게 된 김에 한번 내봐야겠다.