USACO 2024 January Contest (Gold Division)

백준 링크: https://www.acmicpc.net/category/1023

 

1. Walking in Manhattan

 

1. 두 직선의 교점에서 오른쪽으로 가고 있다고 가정하자. 방향을 위로 바꾸는 경우는 시작한 교점의 x좌표와 홀짝성이 다른 가장 가까운 y축에 평행한 직선을 만나는 것이다. 위로 가고 있을 때에도 방향을 바꾸는 경우가 마찬가지이다.

빨간 직선은 x/y 좌표가 홀수인 직선, 파란 직선은 x/y좌표가 짝수인 직선이다

 

따라서 x축과 평행한 각 직선에서 그 다음에 어떠한 직선을 탈지 구할 수 있다.

 

2. $i$번째 직선의 다음 직선을 $f(i)$라고 하자. y축과 평행한 i번 직선, x축과 평행한 j번 직선의 교점을 $(i, j)$로 표현하자. $(i, j)$에서 움직이다보면 $(f^k(i), f^k(j))$로 이동하게 된다. sparse table을 사용해 $f^k(i)$를 빠르게 구할 수 있게 하자. 이분탐색을 사용해서 시간 내에 $(f^k(i), f^k(j))$로 이동할 수 있는 최대 k를 구하자. $(f^k(i), f^k(j))$에서부터 최대 1번 밖에 방향을 안 바꾸기 때문에 나머지는 시뮬레이션을 해주면 된다. 시간복잡도 $O(N+QlogN)$에 해결된다.

2. Cowmpetency

-1. $Q, C$ 제한을 보고 $O(QC)$개의 상태를 가지는 dp 풀이를 생각했다. 이를 위해 구간들의 성질에 대해서 관찰했다.

 

0. $(a_i, h_i)$는 다음과 같이 표현할 수 있다. (그림을 그리면 문제에 대해 생각하기 편하다)

$y_i$는 $i$번째 소의 cowmpetency score이다. 왼쪽 위에 찍힌 점은 [1, a_i] 중 y_i가 최대인 점이다.

 

1. $[a_i, h_i-1]$와 $[a_j, h_j-1]$가 겹친다고 하자. ($a_i < a_j < h_i$)

$max_{k \leq a_j} y_k = max_{k \leq a_i} y_k$이다. 따라서 $(a_j, h_j)$의 조건이 $(a_i, h_j)$와 동치가 되고, $h_i = h_j$가 아닌 이상 모순이다. 따라서 끝점이 같지 않은 이상 $[a_i, h_i-1]$와 $[a_j, h_j-1]$은 겹칠 수 없다.

$max_{k \leq a_j} (y_k) = max_{k \leq a_i} (y_k)$

 

$a_i < a_j$이고 $h_i = h_j$라면 $(a_j, h_j)$ 조건을 무시할 수 있다. 이제 $[a_i, h_i-1]$ 구간들은 겹치지 않는다.

 

2. $dp[x][y] = $ 1~x번째 소까지 보았을 때 최대 cowmpetency가 y인 경우의 수로 정의하자. $x$가 주어진 조건들의 끝점인 경우들에 대해서 고려해야 dp 상태가 $O(QC)$로 줄어든다.

 

dp 전이는 3가지가 있다.

1) $x=a_i$ -> $x=h_i-1$

$dp[h_i-1][y] = dp[a_i][y] \times$ { ($h_i-a_i-1$)개의 cowmpetency를 $y$ 이하로 정하는 경우의 수}

 

2) $x=h_i-1$ -> $x=h_i$

$dp[h_i][y] = \sum_{y' < y} dp[h_i-1][y']$

 

3) $x=h_i$ -> $x=a_j$

$dp[a_j][y] = dp[h_i][y] \times $ { ($a_j - h_i$)개의 cowmpetency를 $y$ 이하로 정하는 경우 수 }

$ + \sum_{y'<y} dp[h_i][y'] \times $ { ($a_j-h_i$)개의 cowmpetency의 max를 $y$로 하는 경우의 수 }

 

각각의 dp 전이를 $O(logN)$에 구할 수 있어, 전체 문제를 $O(QClogN)$에 해결할 수 있다.

 

3. Nap Sort

$a_i$를 오름차순으로 정렬하고 시작하자.

 

1. Bessie pile에 들어가는 원소 개수를 $K$로 고정하고 생각해보자.

Bessie pile에 들어간 원소 중 $i$번째로 작은 원소는 $t_i = K+(K-1)+ \ldots + (K-i+1)$의 시간에 추가된다. 문제는 다음과 같이 환원된다.

 

$N$개의 원소들 중 $K$개의 원소를 선택했을 때, $i$번째로 선택한 원소의 값과 $t_i$ 사이에 수가 있으면 안 된다.

검은색 동그라미는 Bessie pile에 들어가는 원소, 흰색 동그라미는 Helper pile에 들어가는 원소이다.

오른쪽에 있는 동그라미일수록 값이 크다. 검은색 동그라미가 $i$번째 원소이고 수직선에 표시된 값이 $t_i$이다.

성공적인 sorting의 예시, K=3

2. 모든 원소를 Helper pile에 넣어버리면 당연하게 sorting이 되고, 이때 걸린 시간은 $a_n$이다.

 

$K$를 고정하고 마지막 원소를 Bessie pile에 넣어보자. 그러면 마지막 원소와 $t_K$ 사이에 있는 원소들은 모두 Bessie pile에 들어가야 한다.

 

마지막 원소를 Bessie pile에 넣으면 파란색 원소들 역시 Bessie pile에 들어가게 된다. K=3

Bessie pile에 새로 넣는 원소(뒤에서 $i$번째)와 $t_i$ 사이에 있는 원소들을 모두 Bessie pile에 넣는 작업을 반복해주자. $K$번째부터 첫번째 원소까지를 모두 배정했음에도 불구하고 Bessie pile에 들어갈 원소가 있으면 sorting 실패이다.

그런 원소 없이 Bessie pile에 원소들을 넣었다고 가정하자. 그렇다면 아직 Bessie pile에 넣지 않은 앞부분의 원소들에게 적당히 pile을 배정할 수 있다. 

 

3. $N$개의 원소가 있고 $K$가 고정되었다고 하자. 이에 대응하는 sorting이 항상 존재한다. $N$에 대한 귀납법으로 증명하자.

 

1) $N=K$이라면 모든 원소를 Bessie pile에 넣어준다

2) $N>K$라고 가정하자.

$a_N \geq t_K$라면 $a_N$을 Helper pile에 넣어주자. 나머지 원소들은 귀납에 의해 sorting할 수 있다.

 

$a_N < t_K$라면 $a_N$을 Bessie pile에 넣어주자. 나머지 원소들은 귀납에 의해 sorting할 수 있다.

4) $i$를 고정해보자. $K$가 줄어들면 $t_{K-i}$가 감소한다. 따라서 $K$가 줄어들면 마지막 원소를 Bessie pile에 넣었을 때 Bessie pile에 순차적으로 들어가게 되는 원소가 증가한다. $K$를 감소시키면서 2)의 과정을 two pointer를 사용해서 진행하자. 정렬을 제외하고 $O(n)$에 문제를 풀 수 있다.