2023 Sogang Programming Contest Open

지문에서 주어진 정보는 다음과 같습니다.

- $l_t=r_t$이라면 재미도가 $1$ 오릅니다.
- $t\geq 2$인 경우,
  - $l_t = l_{t-1}$이라면 재미도가 $1$ 오릅니다.
  - $r_t = r_{t-1}$이라면 재미도가 $1$ 오릅니다.

`if`-문을 이용하여 답을 구할 수 있습니다. 빠른 입출력 방법을 사용하지 않으면 시간 초과를 받을 수 있음에 유의합니다.


점수가 가장 높은 순열을 구하는 문제입니다.

각 원소가 몇 개의 연속 부분 수열에 속하는지 생각해 봅시다. 가운데에 있을수록 더 많은 연속 부분 수열에 속하는 것은 자명합니다. 따라서 가운데에 있을수록 더 큰 값을 갖도록 순열을 구성하면 됩니다.

$N$이 $4$일때, 정답으로 가능한 순열로는 $[1, 3, 4, 2]$, $[1, 4, 3, 2]$, $[2, 3, 4, 1]$, $[2, 4, 3, 1]$이 있습니다.

사람들의 번호는 서로 다르다는 것에 집중해 봅시다.

$i$번 사람과 $j$번 사람이 배정받은 집을 교환할 수 있고, $j>i$라고 가정해 봅시다.이때 $A_i > A_j$를 만족한다면, 두 사람은 집을 교환하는게 이득입니다.

사람들의 번호는 서로 다르기 때문에 위의 상황에서 세금의 감면되는 양은 순증가합니다. 따라서 최적해에서는 $j>i$ 이면 $A_i \leq A_j$를 만족합니다.

결론적으로 집을 교환가능한 사람들의 부분 수열을 오름차순 정렬하는 것이 주어진 쿼리의 결과라고 할 수 있고, 유일하게 결정됩니다.

$N$이 $300$ 이하이므로 쿼리마다 나이브하게 정렬해주면 문제가 해결됩니다.

$x$의 배수들은 $x$와 서로소가 아닙니다. 마찬가지로 $y$의 배수들은 $y$와 서로소가 아닙니다.

따라서 $x$에서 $xy$로 간 후, 다시 $y$로 가면 문제가 해결됩니다.


$\mathit{DP}$를 다음과 같이 정의합시다.
$$
\mathit{DP}_i = (i\text{번째 시각에 무조건 '어?'를 외칠 때, 최종 혼란의 최댓값})
$$

이때, 다음 점화식이 성립합니다.
$$
\mathit{DP}_i = \max_{t_j<t_i-b_i} (\mathit{DP}_j) + c_i
$$

구하고자 하는 답은 $\max_{1\leq i \leq N} \mathit{DP}_i$입니다. 하지만 이 방법의 시간복잡도는 $O(N^2)$이므로, 시간 초과가 발생합니다.

$\mathit{PF}$를 다음과 같이 정의합시다.
$$
\mathit{PF}_i = \max_{1\leq j \leq i} \mathit{DP}_j
$$
추가로, $k = (t_j<t_i-b_i\text{를 만족하는 }j\text{의 최댓값})$이라고 합시다. 이 때 점화식은 다음과 같이 바꿀 수 있습니다.

$$
\mathit{DP}_i = \mathit{PF}_k + c_i
$$

$\mathit{PF}$를 미리 구해 놓으면, $k$는 이분 탐색으로 찾을 수 있습니다. 따라서 $O(N\log N)$에 해결할 수 있습니다.

우선, union-find를 이용하여 연결된 잡초를 하나의 그룹으로 합칩시다. 배열 $dist$를 다음과 같이 정의합시다.

$$
    dist_i = (i\text{번 그룹에 속한 잡초들만 봤을 때, 원점과의 거리 중 최솟값})
$$

마지막에 방문하는 그룹은 $dist_i$만큼 이동해야 합니다. 나머지 그룹은 $2 \times dist_i$만큼 이동해야 합니다. 즉, $dist$가 최대인 그룹을 마지막에 방문하는 것이 이득입니다.

답은 $2 \times (\sum dist) - \max(dist)$입니다.


$2$번 연산을 잘 관찰해 문제를 해결해 봅시다.
- $2$번 연산만 수행해서는 $A_1$과 $A_N$을 동일하게 만들 수 없습니다.
- $A_i$와 $A_j$가 동일한다면 구간 내 모든 원소가 동일하게 됩니다.
따라서 다음과 같은 방법을 생각할 수 있습니다.
$A_1$과 $A_N$을 동일하게 만든 후 $2$번 연산을 사용합니다.
다음과 같은 두 가지 방법이 있습니다.
- $A_1$과 $A_{N-1}$을 동일하게 만든 후 $1$번 쿼리를 날린다.
- $A_2$과 $A_N$을 동일하게 만든 후 $1$번 쿼리를 날린다.

다음과 같은 $3$가지 방법 안에 $A_1$과 $A_{N-1}$이 같아지거나, $A_2$가 $A_N$과 같아집니다.
- $[2, \: 1, \: N]$ 쿼리를 날린다.
- $[1, \: 1]$ 쿼리를 날리고 $[2, \: 1, \: N]$ 쿼리를 날린다.
- $[1, \: N-1]$ 쿼리를 날리고 $[2, \: 1, \: N]$쿼리를 날린다.
위 내용은 $A_1, A_2, A_{N-1},A_N$의 대소 관계를 비교하면 쉽게 증명할 수 있습니다.

따라서 전체 문제는 $4$번의 연산 안에 해결됩니다.

파노라마로 사진을 찍었을 때 나무가 보이는 순서는 각도 정렬된 순서와 같습니다. 따라서 나무들이 위치한 점들을 각정렬 했을 때 동일하게 정렬되는 점들의 집합을 찾는 문제가 됩니다.

먼저, 간단하게 나무가 $2$개일 때를 관찰해 봅니다. 아래 그림에서 파란 점선은 $2$개의 나무를 이은 직선입니다.

![](https://static.solved.ac/arena/editorial/13/same-scene-solution-01.png)

파란 점선을 기준으로 왼쪽과 오른쪽에 위치한 두 점에 의한 각정렬 순서는 반대가 되는 걸 알 수 있습니다. 반대로 같은 반평면에 위치한 점들은 모두 각정렬 순서가 보존된다는 사실도 쉽게 관찰할 수 있습니다.

나무에 대응되는 $N$개의 점들을 호영이의 위치에서 각정렬한 순서대로 $a_1, a_2, \cdots , a_N$으로 표현한다고 합시다. $a_1 < a_2 < \cdots < a_N$으로 표현 가능합니다.

만약 우진이의 위치 중 하나의 위치인 $b$에서 $a_1 < a_2, a_2 < a_3, \cdots, a_{N-1} < a_N$을 만족하면 $a_1 < a_2 < \cdots < a_N$을 만족한다는 건 쉽게 보일 수 있습니다(단, 이는 모든 나무가 반평면 위에 존재하기 때문에 가능한 판단임에 주의합니다).

같은 방식을 사용해서 호영이의 위치에서 각정렬한 순서대로 $2$개씩 점을 이어서 만들어진 직선들로 순서가 보존되는 구간을 만들어낼 수 있습니다.
지금까지의 풀이대로 하면 아래와 같은 그림이 그려집니다. $x$-축 아래쪽의 점이 호영이의 위치이며 노란 점선은 각정렬된 순서를 표시하기 위해 그린 보조선입니다.

![](https://static.solved.ac/arena/editorial/13/same-scene-solution-02.png)

순서가 보존되는 구간의 최댓값과 최솟값만 구해서 이분탐색을 이용해 해결하면 됩니다. 혹은 시간복잡도가 충분하니 브루트포스 알고리즘으로 해당 구간 안에 포함되는 점의 개수를 직접 세도 됩니다.