ICPC 2021 Seoul Regional I번 Postman

문제 링크: https://www.acmicpc.net/problem/23573

23573번: Postman

 

$t=2$일 때 풀어보자. 시작점($x=0$)과 끝점이 정해진다. 각각 $s$, $e$라고 하자.

편의상 $s<e$라고 하자. 그리고 점 번호를 x좌표 순으로 1, 2, ... N+1번으로 붙이자. (x=0 때문에 점이 하나 더 추가된다)

 

예외적인 케이스를 제외한 $1 < s$, $e-s>1$, $e<N+1$인 경우에 대해서 살펴보자.

 

우선 이동이 불가능한 경우부터 알아보자. 앞으로 오른쪽으로 이동하는 횟수를 $r$로 쓴다.

오른쪽으로 2번 이동

$2 \leq r \leq N-1$이어야 한다. 이제 각 경우에 대해서 최소 이동거리를 구해보자.

 

이동거리는 인접한 두 점 사이를 오간 횟수가 적을수록 좋다. 구체적으로, i번 점과 i+1번 점 사이 거리를 $d_i$라고 하고 두 점 사이를 이동한 횟수를 $c_i$라고 했을 때, 이동거리는 $\sum_{i} c_id_i$이다.

 

$r$ 제한이 없는 경우 이동거리의 최솟값을 구해보자. $s$보다 왼쪽에 있는 $i$에 대해서는 $c_i \geq 2$이다. $s$에서 $i$로 이동하는데 1번, $i$번에서 $e$로 이동하는데 1번이 필요하다. $e$보다 오른쪽에 있는 $i$에 대해서도 마찬가지이다. $s$와 $e$ 사이에 있는 $i$에 대해서는 $c_i \geq 1$이다.

 

모든 등호를 만족시키는 경우는 다음과 같다.

$e-s \leq r \leq n-2$인 경우에 최단거리로 이동할 수 있다.

 

$r=n-1$인 경우의 경로는 한 가지이다.

 

$r<e-s$인 경우에는 이동거리가 어떻게 될까? 몇 가지 관찰을 할 수 있다.

• $s \leq i < e$인 $i$에 대해서 $c_i$는 $2$ 이상의 짝수이고, 나머지 경우에는 $1$ 이상의 홀수이다.
• $s < i < e-1$이고 $c_i=1$이라면 $i+1$번 정점에서 출발할 때에는 오른쪽으로 향한다.
• $1$번 정점에서는 오른쪽으로 향한다.
• $2$번부터 $s+1$번 정점 중 하나는 오른쪽으로 향한다. 그렇지 않다면 $1$번부터 $s-1$번 정점까지의 indegree의 합이 $s$ 이상이어야 한다.

 

따라서 $s$와 $e-1$ 사이에 $c_i=1$인 $i$의 개수는 $r-2$개 이하이어야 한다. 이 조건까지 추가한 이후에 등호를 만족시키기 위해서는 $s < i < e-1$인 정점들 중 $d_i$가 작은 순으로 $r-2$개의 정점은 $c_i=1$이고, 나머지 정점들은 $c_i=3$이어야 한다. 그리고 $i \leq s$ 또는 $i \geq e$인 경우에는 $c_i=2$이어야 한다. 실례는 다음과 같다.

빨간색 간선은 ci=1인 간선들이다.

모든 경우에 대해서 답을 구했다! 이제 $1 < s$, $s < e-1$, $e<N+1$ 조건을 제외한 예외 케이스 처리를 해주자.

편의상 $r$ 제한을 제거한 경우의 최소 이동거리를 $K$라고 하자. 3개의 조건 $1=s$, $s=e-1$, $e=N+1$에 대해서 만족한다면 o, 만족하지 않는다면 x로 표기했다.

 

(o, o, o) $r=1$, 이동거리는 $K$이다.

(o, o, x), (x, o, o) $1 \leq r \leq N-1$, 각 경우에 대해 이동거리는 $K$이다.

(x, o, x) $1 \leq r \leq N-1$이다. $1 \leq r \leq N-2$의 경우 이동거리는 $K$이고, $r=N-1$의 경우 이동거리가 $K+2d_s$이다. 

(o, x, o) $2 \leq r \leq N$이다. $c_1=c_N=1$이고 $d_i$가 큰 $r-2$개 정점에 대해에 대해 $c_i=1$, 나머지는 $c_i=3$이다.

(o, x, x), (x, x, o) $r=N-1$일 때 이동거리가 $K$인 것 이외에는 (x, x, x)와 같다.

 

이제 $t=1$일 때를 풀자. 가능한 모든 $e$에 대해 $t=2$인 경우의 답을 구한 뒤 최솟값을 구하자.

모든 $t=2$인 문제는 $s < i < e-1$인 정점 중 $d_i$가 작은 $r-2$개의 정점의 $d_i$ 합 구하기 부분을 제외하고 $O(1)$에 풀 수 있다. 모든 $e$에 대해서 위의 값을 전처리해주자. 이는 priority_queue를 사용하면 쉽게 해결할 수 있다. 따라서 문제를 $O(NlogN)$에 해결할 수 있다.