_

1. A

앞에서 부터 숫자를 2개씩 보면서 만약 두 수가 같으면, 두 수 모두 답안에 추가해주고 만약 두 수가 다르면 0만 답에 추가해주면 최대 절반만 원래 수열에서 지우므로 조건을 만족하는 답을 찾을 수 있다.

2. B

모든 테스트 케이스에 대한 $N$의 합이 $10^3$ 이하이므로 모든 테스크 케이스에 대해 $O(N^2\log N)$ 시간복잡도로 문제를 해결할 수 있다.

$i$번쨰 위치의 원소를 선택할 때, Greedy Algorithm을 사용하여 남은 원소들 중에서 $c_x = GCD(b_1, ..., b_{i-1}, b_x)$가 최대가 되는 $x$중에 아무 값이나 선택하면 된다. 따라서 원소들을 $(c_x, b_x)$ 꼴 Pair로 Vector에 저장한 다음, 오름차순으로 정렬하였을 때 마지막 위치의 $b_x$ 값을 답안의 $i$번째 위치로 추가한 다음 남은 원소들의 $c_x$값을 갱신해주면 된다.

3. C

C. Chocolate Bunny

Communication Problem이다.

$p_x<p_y$라 가정하면, ? x y는 $p_x mod p_y = p_x$를 리턴할 것이고, ? y x는 $p_y mod p_x < p_x$를 리턴할 것이므로, ? x y와 ? y x중 더 큰 값이 $p_x$와 $p_y$중 더 작은 값임을 알 수 있다. 따라서, 2번의 쿼리로 임의의 두 원소 중 더 작은 원소의 값을 알 수 있기 때문에, $2N-2$번 쿼리를 통해 1부터 $N-1$까지의 값을 갖는 원소들의 위치를 찾을 수 있다. 마지막으로 남은 숫자가 $N$의 값을 갖는 원소이므로 $2N-2$번의 쿼리로 순열을 찾아낼 수 있다.

4. D

D. Discrete Centrifugal Jumpse

만약 한 건물에서 점프해서 올 수 있는 위치를 모두 구하면 다음과 같이 DP으로 풀 수 있다.

$$dp(i) = \min_{j \in jump(i)} (dp(j) + 1)$$

그러면 점프해서 올 수 있는 곳을 구해야 한다. 조건 2와 3이 대칭이므로 조건 2에 대해서 서술하면, $i$번째 건물에서 올 수 있는 위치를 구하는 것을 생각해보자. $i - 1$번째 건물부터 $0$번째 건물까지 누적 최댓값을 만들게 되었을 때, 값이 변하는 위치에서만 후보가 있다. 다른 위치에서는 그 건물의 높이와 $i$번째 건물의 높이의 최솟값보다 큰 건물이 존재하기 때문이다.

값이 변하는 부분만 필요하므로, 스택을 사용해서 관리할 수 있다. $i$번째 건물을 스택에 넣으려고 하면 스택 위쪽에 $i$번째 건물보다 낮거나 같은 건물들을 모두 빼면 스택 내부는 항상 값이 변하는 위치만 저장된다. 또한 모든 원소가 스택에 한 번 들어가고 한 번 빠져나오므로 시간복잡도는 $O(n)$이 된다.

이제 점프할 수 있는 위치들을 구하자. 점프할 수 있는 위치들은 후보들 중 $i$보다 작은 건물들이고 나머지 후보 중 가장 작은 건물까지 점프해서 올 수 있는 건물들이다. 그 이외의 후보들에 대해서는 $i$번째 건물이 높이가 다른 건물보다 작은데, 그 사이에 있는 건물 중 더 큰 건물이 있기 떄문에 점프할 수 없다.

따라서 스택에서 뽑아지는 원소들이 점프할 수 있는 위치들이고 위와 같은 이유로 시간복잡도는 $O(n)$이다.

5. E

E. Egor in the Republic of Dagestan

문제에서 주어진 방향 그래프에서 모든 에지의 방향을 반대로 뒤집은 다음 $N$번 정점에서 색깔이 $i$인 $j$번째 정점까지 최단거리를 $dist[i][j]$라 하자. 최종적으로 $i$번째 정점의 색깔은 $dist[0][i]$와 $dist[1][i]$중 큰 값으로 정해질 것이며, 이렇게 $i$번째 정점의 색이 정해지면 $N$번 정점부터 $i$번 정점까지 최단 거리가 정해진 것이므로 마찬가지로 $i$와 이어진 정점들의 $dist$를 채워나갈 수 있으므로 이를 반복하면 BFS를 이용하여 $dist[i][j]$ 값들을 채워나갈 수 있다.

BFS를 모두 진행하였을 때 $1$번 정점의 색이 정해지는 경우 $1$번 정점부터 $N$번 정점까지 최단 거리를 최대화하는 방법이 정해진 것이다. 하지만 $1$번 정점의 색이 정해지지 않은 경우, $1$번 정점에서 $N$번 정점까지 도달할 수 없도록 정점들의 색을 정할 수 있다는 뜻이 된다.

BFS가 끝났을 때 아직 색이 정해지지 않은 정점들은 3가지가 있을 수 있는데, $dist[0][i]$만 결정된 경우 그 정점의 색을 1로 정해주면 되고, 마찬가지로 $dist[1][i]$만 결정되었으면 그 정점의 색을 0으로 정해주면 된다. 만약 두 값이 모두 결정되어있지 않으면 정점의 색으로 아무 값을 정하여도 상관이 없다. 이렇게 색이 정해지지 않은 정점의 색을 정해주면 $1$번 정점부터 $N$번 정점까지의 최단거리를 최대화할 수 있다.