solved.ac Grand Arena #4 (mirror of Grand Arena Party)

문제가 요구하는 일은 두 가지입니다.

- $A+B-C$를 계산하기.
- $A$와 $B$를 차례로 이어 붙이고, 수로 변환한 후에 $C$를 빼기.

이를 위해서 우리는 문자열과 수를 서로 변환할 수 있어야 합니다. 다음은 각 언어가 지원하는 문자열과 수를 변환하는 함수입니다. 자세한 사항은 각 언어의 레퍼런스를 참고하시기 바랍니다.

|언어|문자 > 수|수 > 문자|
|:-:|:--:|:--:|
|C| `sscanf` | `sprintf`|
|C++| `stringstream`, `stoi`| `stringstream`, `stoi`|
|Python| `int` | `str`|
|Java| `Integer.parseInt` | `String.format`|
|Rust| `i32::parse()` | `format!`|
|Javascript| `+`, `-` | `+`, ` `` `|


solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - A - Editorial

$i$번째 수부터 $j$번째 수까지가 오름차순으로 배열되어있기 위해서는, $i \le k < j$를 만족하는 모든 정수 $k$에 대해 $A_k < A_{k+1}$을 만족해야 합니다.
조건은 인접한 두 수를 비교하는 것만으로 판단할 수 있습니다. 즉, $B_k$를 $A_k < A_{k+1}$을 만족하는지 여부에따라 `True` 혹은 `False`로 나타내면, $i$번째 수부터 $j$번째 수까지가 오름차순이라는 것은, $B_i, B_{i+1}, \cdots, B_{j-1}$ 모두가 `True`라는 것입니다. 

이런 $(i, j)$를 세는 방법은 여러가지가 있습니다. 

- $i = j$ 인 경우에는 항상 오름차순으로 나열되어 있기 때문에, 경우의 수는 기본적으로 $N$이 됩니다.
- $i \ne j$는 연속된 `True`의 블럭을 생각해봅시다. 이 블럭 내부에서 아무렇게나 시작점과 끝점을 잡는 것이 됩니다. 블럭의 길이가 $k$이라면, 서로 다른 두 시작점과 끝점을 잡는 경우의 수는 $\frac{k(k+1)}{2}$입니다. 

답은 $B$에서 연속된 `True` 블럭 길이 $k$에 대해 $\frac{k(k+1)}{2}$를 모두 더한 것에 $N$을 더한 것이 됩니다.  모든 연산은 $\mathcal O (N)$에 처리할 수 있습니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - B - Editorial

로봇 청소기가 작동을 중지할지 판별하기 위해서는 이후 동작들을 시뮬레이션해 보아야 합니다.
시뮬레이션 속의 로봇 청소기는 작동을 중지하는 조건을 만족하더라도 영역을 벗어날 때까지, 혹은 영원히 계속해서 작동할 것입니다.
이때, 정답은 시뮬레이션 속의 청소기가 마지막으로 청소한 시점이 됩니다.

로봇 청소기가 영역을 벗어나는 경우는 직접 시뮬레이션을 하면서 판별하면 됩니다.

로봇 청소기가 영원히 계속해서 작동하는 경우에는, 먼지가 없는 칸들에서 사이클을 반복할 것입니다.
시뮬레이션을 하면서 마지막으로 먼지를 청소한 이후에 방문한 위치들을 기록해 둡시다. 여기서 위치란 로봇 청소기의 좌표 $(r, c)$와 방향 $d$의 쌍을 뜻합니다.
방문 배열에 기록했던 위치를 다시 방문하는 순간 사이클이 형성됩니다.

구현 시 몇 가지 사항을 주의해야 합니다.

- 동일한 좌표 $(r, c)$를 다시 방문한다고 해서 꼭 사이클이 생기지는 않습니다. 동일한 좌표를 동일한 방향으로 방문해야 합니다.
- 먼지를 청소하고 나면 방문 배열을 초기화해야 합니다. 먼지를 청소한 칸 때문에, 같은 위치에서 시작해도 경로가 달라질 수 있기 때문입니다.
- 방문한 위치를 배열에 하나씩 추가하면서 관리하면 사이클 판별 시 배열을 순회해야 하므로 시간이 오래 걸립니다.
  대신 $(r, c, d)$를 인덱스로 하는 3차원 배열을 활용합시다.

시간복잡도 분석은 다음과 같습니다. 로봇 청소기가 먼지를 청소할 때마다, 다음 먼지를 청소하기 전까지 중복 없이 방문할 수 있는 위치의 개수는 $O(HW)$개입니다.
로봇 청소기가 먼지를 청소할 수 있는 횟수는 $O(HW)$이므로, 전체 시간복잡도는 $O((HW)^2)$입니다.

### 다른 풀이 1

로봇 청소기의 위치가 주어지면 그 다음 위치 뿐만 아니라 이전 위치도 유일하게 결정됩니다.
따라서, 사이클이 형성될 때 마지막으로 먼지를 청소한 직후의 위치로 다시 돌아오게 됩니다.
그렇지 않다면 사이클이 처음 형성되는 위치가 두 개의 이전 위치를 가지기 때문입니다 (사이클에 진입하기 직전과 한 바퀴 돌기 직전).

이 사실을 이용하면 방문 배열을 관리하지 않고도 사이클을 판별할 수 있습니다.

### 다른 풀이 2

로봇 청소기가 지금까지 먼지를 $x$번 청소했다면, 다음 먼지를 청소하기 전까지 최대 $4x$가지의 위치를 방문할 수 있습니다. 즉, 로봇 청소기는 정지하기 전까지 아무리 많아도 $4 (1 + 2 + \cdots + (HW-1)) + 1 \le 2(HW)^2$번 이하로 이동합니다. 직접 $2(HW)^2$번 이동을 시뮬레이션한 뒤 마지막으로 청소한 시점을 출력하면 됩니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - C - Editorial

우선, 삼각형의 넓이를 구하는 법을 알아봅시다. 반시계방향으로 주어진 세 점 $(x_1, y_1); (x_2, y_2); (x_3; y_3)$에 대해 세 점이 이루는 삼각형의 넓이는 


$$
\frac{(x_2-x_1)(y_3-y_1) - (y_2 - y_1)(x_3 - x_1)}{2}
$$

로 구할 수 있습니다. 

이제 임의의 다각형의 넓이를 구하는 방법은 다각형을 삼각형으로 분할해서 생각하는 것입니다. $1$번점을 기준으로, 다른 모든 점까지 대각선을 그으면 $1, 2, 3$번 점; $1, 3, 4$번 점; $\cdots$; $1, (N-1), N$번 점으로 이루어진 삼각형이 $N-2$개가 생깁니다. 이 삼각형의 넓이의 합을 구하면 다각형의 넓이를 구할 수 있습니다.

이제, 여기서 절반이 되는 위치를 찾아봅시다. 넓이를 $1$번 점을 기준으로 구하기 때문에, 선분의 한 끝점은 $1$번 점으로 고정합니다. $1, i, (i+1)$번 삼각형의 넓이를 더해나가다가, 다각형 전체 넓이의 절반을 넘어가는 시점이 있습니다. 즉, $1, (k-1), k$번 삼각형까지 더하면 다각형 넓이의 절반이 되지 않지만, $1, k, (k+1)$번 삼각형을 더하면 삼각형 넓이의 절반이 넘어갑니다. 이 때, 답이 되는 나머지 끝 점은 $k, (k+1)$번 점을 잇는 선분 위에 있다는 것을 알 수 있습니다.

이제 내분점의 비율을 구해야 합니다. 높이가 같은 삼각형 넓이의 비율은 밑변의 비율과 같기 때문에, 절반을 만들기 위해 더해져야하는 넓이를 $1, k, (k+1)$번 삼각형의 넓이로 나누면 내분점의 비율을 구할 수 있습니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - D - Editorial

현재 커서가 목록에서 몇 번째 폴더를 가리키는지를 나타내는 변수 $x$와 각 폴더의 펼침 여부를 관리합시다.

DFS 알고리즘을 이용하면 목록에 보이는 모든 폴더를 순서대로 나열할 수 있습니다. DFS를 수행할 때 펼쳐져 있는 폴더는 재귀적으로 탐색하고, 접혀 있는 폴더는 탐색하지 않습니다. 폴더를 방문할 때마다 배열 $L$에 폴더를 추가하면, 폴더가 목록에 보이는 순서대로 배열에 추가됩니다.

먼저 DFS를 통해 $L$을 구한 다음, 쿼리마다 다음을 수행합니다.

- `toggle`: $L$에서 $x$번째 폴더를 찾고 해당 폴더의 펼침 여부를 변경합니다. DFS를 수행하여 $L$을 다시 구합니다. 시간복잡도는 $O(N)$입니다.
- `move` $k$: $x$에 $k$를 더한 뒤, $L$의 인덱스 범위를 벗어난 경우 범위 내 값으로 다시 설정합니다. 시간복잡도는 $O(1)$입니다.

전체 시간복잡도는 $O(NQ)$입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - E - Editorial

최적화 문제를 결정 문제로 바꾸어 해결하는 Parametric search 기법을 활용한 풀이입니다.

먼저 $M$개 중 $X$개의 전자기기를 연결할 수 있는지 판별해 봅시다. 다음과 같은 그리디한 성질을 이용합니다.

- 전자기기를 선택할 때에는 벽과의 거리 제한 $D_i$가 큰 것부터 $X$개를 선택하는 것이 좋습니다.
- 멀티탭을 연결할 때에는 소켓 수 $A_i$가 많은 것부터 벽면에 가까이 연결하는 것이 좋습니다.

연결이 가능한지 판별하기 위해 다음과 같이 연결을 구성해 봅시다.

맨 처음에는 벽과의 거리가 $0$인 소켓 $K$개가 열려 있습니다. 현재 열려 있는 소켓들의 벽과의 거리가 $d$라고 할 때, $X$개의 전자기기 중 거리 제한이 $d$인 전자기기들을 우선 연결합니다. 그 후, 남은 멀티탭 중 소켓 수가 많은 것부터 나머지 소켓들에 연결합니다. 이제 열린 소켓들의 거리가 $d+1$이 되었으므로 위 과정을 반복합니다.

도중에 소켓이 부족해진 경우 $X$개의 전자기기를 모두 연결하는 것이 불가능합니다. 도중에 전자기기를 모두 소진했다면 연결 성공입니다. 멀티탭을 모두 소진했다면 열린 소켓 수와 남은 전자기기 수를 비교하여 연결 가능 여부를 판별할 수 있습니다.

이제 위 알고리즘을 이용하여 연결 가능한 최대 전자기기 수를 구할 차례입니다. $X$에 대한 이분 탐색을 진행하면서, 위 방법을 이용해 $X$개의 전자기기를 연결 가능한지 확인합니다. 연결 가능하면 더 큰 개수 범위를, 불가능하면 더 작은 개수 범위를 탐색합니다. 그러면 $O(\log M)$번의 탐색만에 연결 가능한 최대 전자기기 수 $X$를 구할 수 있습니다. 총 시간복잡도는 $O((N+M) \log M)$입니다.

solved.ac Grand Arena #4 (mirror of Grand Arena Party) (Div. 2) - F - Editorial

문제에 적힌 사항을 그대로 $1$초씩 시뮬레이션 하는 코드를 구현할 수 있습니다. 시뮬레이션의 한 단계는 $O(N+L)$정도의 시간이 걸립니다. 이제, 각 선택지마다 어떤 선택지를 고를지를 백트래킹을 사용해서 모두 구해보면, 가능한 선택지가 총 $\mathcal O (2^N)$개가 있기 때문에, $\mathcal O(2^N \times (N+L))$ 만큼의 시간이 걸립니다.

하지만, 이 백트래킹 과정에서 버섯들의 상태로 가능한 것이 $\mathcal O (2^N)$까지 발산하지 않는다는 것을 알 수 있습니다. 실제로 가능한 상태의 개수는 $\mathcal O(N^2L)$개 정도입니다. 그렇기 때문에 백트래킹 과정을 Memoization등을 이용해서 최적화하면 $\mathcal O(N^2L(N+L))$ 시간이 걸린다는 것을 알 수 있습니다.

별해로, $K=1$인 답이 항상 존재한다는 것을 관찰해서, $\mathcal O(N(N+L))$ 시간에 문제를 해결하는 법도 있습니다.

버섯들의 상태로 가능한 것이 $\mathcal O (N^2L)$개밖에 없다는 사실, $K=1$인 답이 항상 존재한다는 것을 증명하는 것은 추가적인 관찰이 필요합니다. 이는, Div1F의 에디토리얼을 참고해주시기 바랍니다.

언어	문자 > 수	수 > 문자
C	`sscanf`	`sprintf`
C++	`stringstream`, `stoi`	`stringstream`, `stoi`
Python	`int`	`str`
Java	`Integer.parseInt`	`String.format`
Rust	`i32::parse()`	`format!`
Javascript	`+`, `-`	`+`, ``