본문 바로가기

코딩/국대 멘토링 교육

2021 국대 멘토링 일지 - 3주차

이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다.

#1. Just Long Neckties (0:00 ~ 0:06)

만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다.

 

Time Complexity: $O(N \log N)$

 

#2. JJOOII 2 (0:06 ~ 0:18)

각 문자로부터 오른쪽에 있는 가장 가까운 J, O, I의 위치를 $O(N)$에 구할 수 있고, 이것을 sparse table의 형태로 만들 수 있습니다. 이렇게 하면 각 문자로부터 $k$번째 J, O, I의 위치를 $O(\log N)$에 구할 수 있습니다.

 

문제를 조금 변형하면 JJ..JJOO..OOII..II를 부분 수열로 포함하는 가장 짧은 부분 문자열의 길이를 구하는 문제가 되기 때문에, 그 시작점을 모두 해 보면서 sparse table을 이용해 가능한 가장 왼쪽 끝점을 $O(\log N)$에 구하는 식으로 계산해줄 수 있습니다.

 

Time Complexity: $O(N \log N)$

 

#3. Collecting Stamps 3 (0:18 ~ 0:39)

$DP[i][j][k]$: 현재까지 $1$번부터 $i$번 도장의 위치, 그리고 $j$번부터 $N$번 도장의 위치에 모두 방문한 적이 있고, 현재 $i$번 도장의 위치에 서 있으며 현재까지 얻는 데 성공한 도장이 $k$개일 때의 최소 시각으로 정의합니다.

 

$DP2[i][j][k]$는 위의 정의와 같지만 현재 위치가 $j$번 도장의 위치인 경우로 정의합니다. 단, 0번 도장의 위치는 0이며, $N+1$번 도장의 위치는 0이라고 생각합니다.

 

이렇게 하면 $DP[0][N+1][0] = DP2[0][N+1][0] = 0$으로 초기값을 설정할 수 있고, $DP[i][j][k]$에서 $DP[i+1][j][k]$, $DP2[i][j-1][k]$로 가는 전이를 어렵지 않게 찾아낼 수 있습니다. 이들을 모두 계산해 최소 시간이 $\infty$이 아닌, 가능한 점수의 최댓값을 구해 주면 됩니다.

 

Time Complexity: $O(N^3)$

 

#4. Olympic Bus (0:39 ~ 1:25)

각 간선을 뒤집은 뒤의 정점 1부터 N까지의 최단 거리를 구하는 방법을 찾으면 됩니다. 일단 기존 상태에서 아무 최단 경로를 하나 찾습니다.

 

1. 현재 간선이 최단 경로에 포함된 경우

이 경우는 다익스트라를 다시 돌려 최단 거리를 다시 찾습니다. 시간이 오래 걸릴 것 같아 보이지만, 이러한 간선은 최대 $N$개이므로 다익스트라를 최대 $N$번 돌리게 됩니다. 다익스트라의 $O(N^2)$ 구현을 사용하면 이 경우는 $O(N^3)$에 처리됩니다.

 

2. 현재 간선이 최단 경로에 포함되지 않은 경우

기존의 최단 경로 또는 뒤집힌 현재 간선을 통과하는 경로 둘 중 하나가 최적입니다. 전자는 전처리해 두고, 후자는 정점 1부터 각 정점까지의 최단 경로, 각 정점부터 정점 $N$까지의 최단 경로를 전처리해 두면 해결됩니다. 밑줄친 부분이 뒤집힌 간선을 포함하면 답이 틀리게 나올 수 있다고 생각하실 수도 있는데, 어차피 기존에 이 경로는 최단 경로가 아니었으므로 만약 그러한 상황이 발생한다면 최단경로보다 더 길어질 것이기 때문에 답이 될 수 없음을 알 수 있습니다.

 

Time Complexity: $O(M \log N + NM + N^3)$ (may vary by implementation)

 

#5. Fire (1:25 ~ 3:44)

x축을 위치로, y축을 아래로 갈수록 시간 t가 증가하는 형태로 생각하고 각 칸의 값을 격자에 적어 보면, 같은 값을 가지는 칸의 형태가 아래와 같은 평행사변형이 됩니다.

이 모양은 아래 그림과 같이 아래로 무한한 직각삼각형의 합으로 나타낼 수 있습니다.

 

아래로 무한한 직각삼각형 모양을 segment tree에 업데이트하는 방법은 다음과 같습니다.

이렇게 사다리꼴 모양을 업데이트할 수 있으면, 사다리꼴에서 직사각형을 빼면 됩니다. 사다리꼴을 업데이트하기 위해서는 좌표평면 전체를 기울이면 됩니다.

이런 형태로 만들면 사다리꼴이 직사각형이 되고, 따라서 lazy segment tree를 두 개 관리하면 맞을 수 있습니다. 저는 시간 초과가 떠서, lazy fenwick tree의 형태로 관리했습니다.

 

필요한 직각삼각형은 사전에 segment tree에서의 이분 탐색을 통해 구해 놓을 수 있으므로, 직각삼각형을 구하는 것과 답을 구하는 과정을 시간에 대한 sweeping으로 동시에 구해 나가면 문제를 풀 수 있습니다.

 

Time Complexity: $O((Q+N) \log N)$

'코딩 > 국대 멘토링 교육' 카테고리의 다른 글

2021 국대 멘토링 일지 - 3주차  (0) 2021.04.24
2021 국대 멘토링 일지 - 1주차  (0) 2021.04.05