2022 ICPC Seoul Regional 후기

---

안녕하세요 Gliver 입니다.

이번 글은 2022.11.19 에 있었던 2022 ICPC Seoul Regional에 대한 글입니다.

 

운이 좋게 본선을 나갈 수 있게 되어 지난 예선 글에 이어서 본선 관련한 글을 써볼까 한다.

대회가 끝난 직후부터 시험과 프로젝트 때문에 거의 한 달이 지난 지금에야 글을 쓸 수 있게 되었다..

 

 

최종 스코어보드

이번 대회 또한 예선과 비슷한 전략으로 진행하게 되었다.

(나와 α가 주로 키보드를 잡았으며 β는 보조를 주로 하였다)

 

이번 대회에서는 내가 E, I를 풀었고, α가 F, J를 풀었다.

(참고로, 대회 문제는 여기에서 풀어볼 수 있다)

 

 

 

J. Parentheses Tree (00:37) [+1]

처음에 나는 β와 I를 풀고, α는 J를 풀기로 했다.

α가 J를 처음 제출했을 때 틀려서 봤는데 long long으로 선언을 안 해 주어서 틀렸던 것이었다.

이후에 long long으로 바꾼 후에 제출했더니 통과할 수 있었다.

참고로, 코드포스 #819(Div.2) C번과 매우 비슷한 문제인 거 같았다. (이에 관한 내용은 여기를 참고하기 바란다)

 

 

 

I. Palindrome Type (02:01) [+2]

주어진 문자열 $S$에 대해서 최소의 문자를 제거하여 팰린드롬 문자열을 만드는 문제이다.

즉, 문자열 $S$가 최소 몇 개의 문자를 제거해야 팰린드롬 문자열이 되는지를 묻는 것이다.

 

이 문제의 특징이라면 최소 개수 $k$가 $0, 1, 2, 3$일 때만 정확히 구별하고 나머지 경우에 대해선 $-1$을 출력하면 된다는 점이다.

이러한 특징을 알았음에도 이상한 그래프 매칭 형태로 문제를 해석하며 약 2시간 가까이를 소모한 거 같다.

 

다행히도, 다시 정신을 잡고 생각해 보니 문제의 풀이를 생각할 수 있었다.

왼쪽과 오른쪽 맨 끝을 각각 $\small{left}$, $\small{right}$라고 해보자.
$S\small{[left]}$와 $S\small{[right]}$의 문자가 같으면 $\small{left}$, $\small{right}$ 간격을 좁혀가면 된다.

만약, 그렇지 않으면 $S\small{[left]}$ 또는 $S\small{[right]}$를 무조건 삭제해야 할 것이다!
이 두 문자 중 하나를 삭제하지 않는다면 문자열 $S$는 절대 팰랜드롬 문자열이 될 수 없음

같지 않은 경우에 삭제해야 하는 후보는 $S\small{[left]}$또는 $S\small{[right]}$이기 때문에 2가지의 경우로 나누어지고
우리는 $k$를 3까지만 살펴보면 되므로 이 풀이의 시간 복잡도는 최대 $O(2^3 \cdot n)$이라고 할 수 있다.

 

 

 

F. Frog Jump (02:41) [+1]

내가 I를 푸는 동안 α는 F를 풀고 있었으며, 내가 I를 풀자마자 합류하였다.

구간들이 여러 개 주어지며 연속된 구간들을 합쳐서 한 개로 보는 문제이다.

 

문제는 여러 개의 구간 정보가 $n$개 주어지며 이때 각 구간을 $k$번 왔다 갔다 해야 한다.

이때, 최소로 점프해야 하는 길이를 구하는 문제이다.

 

$n$과 $k$의 범위를 살펴보면, $n \leq 100,000$, $k \leq 1,000,000$ 이므로

적절한 전처리를 하여 $k$번의 쿼리를 빠르게 처리해야 한다는 점을 알 수 있다.

이러한 문제는 시작점을 기준으로 볼 것이냐 끝점을 기준으로 볼 것이냐를 정하는 것이 중요하다.
이 문제 같은 경우는 시작점을 기준으로 정렬하여 연속된 구간을 합치면 된다.
합친 후에는 누적합을 통해서 각 구간까지의 간격이 얼마인지를 저장해 놓으면 한 쿼리를 $\small{O(1)}$에 처리 가능하다.

누적합 배열을 만드는 데 $O(n)$, 모든 쿼리를 처리하는 데 $O(k)$이므로 이 풀이의 시간 복잡도는 $O(n+k)$이다.

 

 

 

E. Forbidden Turns (04:40)

3문제를 푼 후에 K를 시도해 보았지만 좋은 결과를 내지 못하였고, 약 1시간 30분이 남은 시점에서 E로 갈아타게 됐다.

다행히 이 문제는 접근을 잘 하여 1트만에 풀 수 있었다.

 

노드의 개수는 $n \leq 30,000$, 간선의 개수는 $m \leq 10n$, forbidden turns의 개수는 $k \leq 500,000$ 이다.

이때, 시작점 $v$에서 도착점 $w$로 가는 최단 거리를 구하는 문제이다.

 

만약, forbidden turns라는 존재가 없다면 어떻게 풀 수 있을까?

모든 간선의 가중치 $c_i$는 $\small{0} \leq c_i \leq \small{10^3}$을 만족하므로 그냥 다익스트라로 풀면 된다.

 

그렇다면, forbidden truns가 존재하면 일반적인 다익스트라 문제에서 뭐가 달라질까?

첫 번째 달라지는 점은 forbidden turns라는 이름 그대로 가지 못하는 경로가 생긴다는 점이다.
두 번째 달라지는 점은 같은 노드를 두 번 이상 방문하는 경우가 생긴다는 점이다.
이는 문제의 그림을 보면 쉽게 이해할 수 있을 것이다

 

먼저, 첫 번째 달라지는 점에 대해서 살펴보자.

현재 가려는 경로가 forbidden turns인지 어떻게 알 수 있을까?
가장 간단한 방법으로는 forbidden turns의 리스트를 선형으로 탐색하는 것이다.
하지만 이렇게 처리할 경우에 한 번 살펴 보는 데 $\small{O(k)}$가 걸리니 시간초과가 나게 된다.

따라서, forbidden turns 리스트를 set 자료구조를 이용하여 $\small{(x_i, y_i, c_i)}$ 쌍으로 저장하면 된다.
이 경우는 한 번 접근하는 데 약 $\small{O(log_2 k)}$가 걸리므로 효율적인 방법이라 할 수 있다.

 

다음으로, 두 번째 달라지는 점에 대해서 살펴보자.

같은 노드를 여러 번 방문하는 상황이 생기는 것을 어떻게 처리할까?
이에 대한 해답은 문제를 자세히 살펴 보면 알 수 있다.

같은 노드를 여러 번 방문하는 경우는 생기지만 음수인 간선이 없기 때문에 한 간선을 여러 번 방문(사용)하는 경우는 없다!
이미 한 번 사용한 간선을 또 사용한다면 그때는 해당 노드까지의 최단 거리가 아니라는 점을 인지하자

따라서, 노드를 기준으로 방문 처리하는 것이 아닌 간선을 기준으로 방문 처리를 하면 이를 해결할 수 있다.

 

따라서, 이러한 풀이를 이용하여 다익스트라를 사용하면 약 $O(m \cdot log_2 n  \cdot log_2 k)$의 시간 복잡도로 해결할 수 있다.

 

 

 

느낀점

1학년(2020년) 말부터 시작해서 3학년(2022년) 말까지 해서 약 2년간 조금씩 꾸준히 PS를 한 것 같다.

아직 ICPC와 같은 큰 대회에서의 수상은 갈 길이 멀었지만, 이제는 개발자로 살아가는 데에 있어 필요한 수준은 도달한 거 같다!(?)

 

앞으로 PS는 취미로 하며 내 분야에 맞는 개발 공부에 몰두할 예정이다.

여기에 있어서 2년 간의 PS 경험은 많은 도움이 될 것 같다!