제2회 보라매컵 본선 Open Contest

다음과 같이 조건을 정의해 봅시다.

- $A$ : 병영외 급식을 행복하게 즐길 방법이 존재합니다.
- $B$ : 생활관의 인원 합이 $X$로 나누어떨어집니다.

$A \rightarrow B$ : 가능한 방법의 모든 그룹을 하나의 그룹으로 합쳐봅시다. 각 그룹의 인원은 $X$로 나누어떨어지므로, 합친 하나의 그룹의 인원 또한 $X$로 나누어떨어집니다. 모든 생활관이 정확히 하나의 그룹에만 속하기 때문에, 해당 인원은 생활관의 인원 합과 동일합니다.

$B \rightarrow A$ : 생활관의 모든 인원을 하나의 그룹으로 묶는 것 또한 유효한 그룹입니다. 해당 그룹의 인원수가 $X$로 나누어떨어지므로, 모든 그룹의 인원수가 $X$로 나누어떨어집니다. 따라서, 병영외 급식을 행복하게 즐길 방법이 존재합니다.

따라서 두 조건은 동치입니다. 생활관의 인원 합을 구하고, 해당 값이 $X$로 나누어떨어지는지 판별해줍시다. 

적군들을 상대할 때, 김 병장에게 제일 유리한 상황으로 전투를 한다는 것은 적군들을 상대할 때 김 병장의 전투력이 가능한 최대로 오른 상태에서 전투를 한다는 것입니다. 현재 격파를 하지 못한 적군의 전투력이 $s$라고 합시다.

김 병장에게 제일 유리하게 전투를 하는 방법은 전투력이 $s$ 미만인 적군들 중 가능한 적군들을 모두 격파하여 전투력을 최대로 높인 상태에서 전투를 하는 것입니다. 이는 $s$ 미만의 적군들에게도 동일하게 적용됩니다. 따라서, 김 병장은 적군들을 전투력이 낮은 순서대로 격파하는게 제일 유리합니다.

또한, 아이템은 적군들로부터 얻은 전투력을 두 배로 증폭시켜 주는 역할을 합니다. 그렇다면 아이템은 적군들을 최대한 격파하여 적군들로부터 얻은 전투력이 커진 상태에서 두 배로 증폭시키는게 제일 유리합니다. 따라서, 아이템은 최대한 나중에 사용하는 게 최선의 방법입니다. 전투력이 낮은 순서대로 적군들을 격파하다가 본인보다 전투력이 높은 적을 만나면 본인의 전투력이 적군의 전투력 이상이 될 때까지만 사용하고, 모든 적을 격파한 후에 남은 아이템들을 사용하는 게 제일 유리합니다. 

시간복잡도는 $\mathcal{O}\left(NM\log{M}\right)$입니다. 

각 지점을 노드로, 도로를 거리가 $1$인 간선으로 본다면 문제 상황은 각 노드에서 $1$번 노드로 최단거리로 움직이는 상황이라고 볼 수 있습니다. 이는 역으로, $1$번 노드에서 나머지 노드로 최단거리 경로를 찾아서 이동하는 상황으로 볼 수 있습니다. 간선들의 비용이 $1$이므로 음수 사이클은 생길 수 없습니다. 따라서, 최단거리 경로의 간선만을 남겨두면 $1$번 노드를 루트로 하는 트리가 생성되는 것을 알 수 있습니다.

같은 시간에 차량 두 대 이상이 같은 지점에 도착한 상황은 두 대 이상의 차량들이 해당 지점으로부터 같은 거리만큼 떨어진 것을 알 수 있습니다. 이는 $1$번 노드로부터의 깊이가 동일함을 의미합니다. 따라서, 이 문제는 $1$번 노드를 루트로 하는 트리가 그려졌을 때, 같은 깊이의 노드들을 선택하지 않는 조합이 몇 개 인지를 묻는 문제가 됩니다. 

$N$개의 노드들이 있고, $1$번 노드의 깊이가 $1$일 때, $d_h$를 깊이가 $h$인 노드들의 개수라고 한다면, 아래와 같은 식으로 표현할 수 있습니다.

$$
(d_1+1) \times (d_2+1) \times \cdots \times (d_N+1) - 1
$$

따라서, $1$번 노드를 루트로 하는 트리에서 깊이별 노드 개수를 BFS로 구한 뒤 위 식을 적용하여 풀 수 있습니다. 시간복잡도는 BFS의 시간복잡도인 $\mathcal{O}(N+M)$입니다. 

모든 업무가 선행 업무가 없다면 다음과 같이 DP 식을 정의하여 간단한 배낭 문제로 해결할 수 있습니다.

- $dp[i]$: 처리한 문서들의 중요도 합이 i일때 필요한 최소 처리 시간

선행 업무가 있는 경우 선후행 관계로 엮인 업무들의 집합인 **업무 묶음**들이 존재합니다.

각 업무 묶음에 있는 업무들을 $d_1, d_2, \cdots , d_k$라고 할때 각 업무 묶음들을 처리하는 방법은 $d_1$만 처리하는 방법, $d_1, d_2$를 처리하는 방법, $\cdots$, $d_1 \sim d_k$까지 모두 처리하는 방법까지 총 $k$개의 방법이 있습니다. 따라서 각 방법당 걸리는 시간과 얻을 수 있는 중요도의 합은 $(t_1, w_1)$, $(t_1 + t_2, w_1 + w_2)$, $\cdots$,  $(t_1 + t_2 + \cdots + t_k, w_1 + w_2 + \cdots + w_k)$ 입니다.

즉, DP 테이블을 선행 업무가 존재하지 않는 경우와 마찬가지로 설정하고, 각 업무 묶음을 순회하며 해당 업무 묶음을 처리하는 방법을 모두 DP 테이블에 넣어주면 $\mathcal{O}\left(NS\right)$만에 답을 구할 수 있습니다.


차출이 진행될수록 병사들 사이의 차출 횟수 차이는 점차 줄어들다가 $30N$일의 차출이 이루어지고 난 뒤에는 어떤 두 병사의 차출 횟수 차이도 $1$을 초과하지 않으며 군번이 큰 병사의 차출 횟수는 군번이 작은 병사의 차출 횟수보다 작거나 같게 됩니다.

따라서 $30N$일 이후에는 가동 일수와 병사의 군번을 이용해 해당 병사가 몇 번 더 차출되는지 $\mathcal{O}\left(1\right)$에 구할 수 있습니다.

$30N$일까지의 쿼리는 차출을 시뮬레이션하며 처리하고 그 이후의 쿼리는 아래의 식을 이용해 처리합니다.

시뮬레이션이 끝난 시점의 가동 일수를 $D$, 그때 차출된 마지막 병사의 군번을 $id$라고 하면 쿼리 $(d_i, x_i)$에 대해 $D$부터 $d_i$까지 병사 $x_i$가 차출된 횟수는 다음과 같습니다.

- $N$명을 차출할때마다 $1$번씩, $\lfloor3(d_i - D) / N\rfloor$ 번 차출됩니다.

- $id$에서 $x_i$까지의 거리만큼의 병사가 더 차출되었다면, 즉
  $$
  \left[(x_i - id + N - 1) \mod N \right] \lt \left[ 3(d_i - D) \mod N \right]
  $$
  이면 한번 더 차출됩니다.

시뮬레이션에 $\mathcal{O}\left(N\log{N}\right)$의 시간, 쿼리 정렬에 $\mathcal{O}\left(Q\log{Q}\right)$의 시간이 필요하므로 시간 복잡도는 $\mathcal{O}\left(N\log{N} + Q\log{Q}\right)$입니다. 

예외적으로 $N = 3$인 경우 모든 병사가 매일 차출되므로 병사들 사이의 차출 횟수 차이가 줄어들지 않으며 모든 쿼리의 답이 $d_i$와 동일합니다.

지휘관이 $i$번 적군 참호에게서 국군 배치를 통해 승리하기 위해서는 맞은편의 아군 참호에 최소 $a_i+1$명의 국군을 배치해야 합니다. 이러한 국군의 수를 $b_i$라 합시다. $(b_i=a_i+1)$
그리고 폭탄의 폭파 범위를 $[l, r] (1 \leq l \leq r \leq N)$라 합시다.

어떤 폭파 범위 $[l, r]$ 상태에서 국군 배치로 승리할 수 있는 적군 참호의 최대 개수는 $b_l, b_{l+1}, \cdots, b_r$을 제외하고 $b_i$가 작은 순서대로 아군 참호에 $b_i$명의 국군을 배치할 수 있을때까지 배치하는 방법으로 구할 수 있습니다. 이때 배치할 수 있는 총 국군의 수는 총 $M$명임을 고려해야 합니다. 이러한 방법을 통해 구한 국군 배치로 승리할 수 있는 아군 참호 집합을 $S_{l,r}$이라 합시다.

$n(S_{l, r})+(r-l+1)$이 각 $[l, r]$ 상태에서 승리할 수 있는 최대 적군 참호 개수이며, 따라서 $\max(n(S_{l, r})+r-l+1)$가 참호전에서 지휘관이 폭탄과 국군 배치로 승리할 수 있는 최대 적군 참호 개수입니다.

하지만 모든 $S_{l, r} (1 \leq l \leq r \leq N)$에 대해 승리할 수 있는 최대 적군 참호 개수를 naive하게 전부 탐색하면 최적의 국군 배치를 위한 정렬 연산을 포함하여  $\mathcal{O}(N^3 \log N)$의 시간이 걸립니다. 이를 최적화해봅시다.

$[l, r]$에서 임의의 $l$에 대해 최적의 $r$값은 $a_l+a_{l+1}+\cdots+a_r \leq K$을 만족하는 가장 큰 $r$이며, 각 $l$에 대해 최적의 $r$값만을 탐색해도 문제의 최종 해를 구할 수 있음은 자명합니다. 따라서 각 $l$에 대한 최적의 $r$값을 두 포인터를 활용하여 기록해두면 시간복잡도를 $\mathcal{O}(N^2 \log N)$으로 줄일 수 있습니다. 여기서 시간복잡도를 더 줄이기 위해서는 다음과 같은 관찰이 필요합니다.
- $S_{l, r}$과 $S_{l+1, r}$, 또는 $S_{l, r}$과 $S_{l, r+1}$의 차이는 **최대** 원소 하나 차이밖에 나지 않는다.

따라서 두 포인터로 스위핑하며 $[l, r]$가 이동할 때마다 $S_{l,r}$을 구성하면서 승리할 수 있는 최대 적군 참호 개수를 모두 계산하는 방법으로 시간복잡도를 줄일 수 있습니다.

이 점에서 착안하여 multiset을 활용하면 국군 배치로 승리할 수 있는 아군 참호를 관리할 수 있습니다.
multiset $2$개를 만들어 $[l, r]$에서 항상 다음과 같은 상태가 되도록 관리해주면 됩니다.
- $ms1$: $S_{l, r}$의 각 $b$-값
- $ms2$: $b_l, \cdots, b_r$을 제외한 $b$-값들 중 $ms1$에 포함되지 않은 $b$-값

$[l, r]$의 범위가 이동할 때마다 multiset을 관리하기 위한 시간복잡도는 $\mathcal{O}(\log{N})$입니다. 따라서 전체 시간복잡도는 $\mathcal{O}(N\log{N})$입니다.

별해로 좌표압축을 활용한 풀이, 세그먼트 트리를 활용한 풀이가 있습니다.


문제에서 정의된 덧셈 규칙에 의해, 각 자릿수의 합의 결과는 다른 자릿수 합의 결과에 독립적입니다. 따라서, 현재 대표수와 더했을 때 더 높은 자리에서 $9$에 가깝게 나오는 대표수일수록 점수가 높게 나오게 됩니다. 높은 자리에서의 합의 결과가 같다면, 아랫자리에서의 합이 더 높을수록 점수가 높게 나옵니다.

Trie를 활용하여 대표수들을 십진법으로 표현하여 관리한다면, 특정 대표수와의 합이 제일 높은 대표수를 $\mathcal{O}\left(10N\right)$만에 찾을 수가 있습니다. 현재 대표수와 제일 높은 자리와의 합이 $9$에 제일 가까운 대표수가 존재하는지를 찾고, 이를 만족하는 대표수가 여러개가 있다면 다음 높은 자리에서 합이 $9$에 제일 가까운 수를 그리디하게 찾는 방법으로 찾을 수 있습니다. 

총 시간복잡도는 $\mathcal{O}\left(10NM\right)$입니다.

별해로 set과 이분탐색을 활용한 풀이도 있습니다.


구간 $[l, r]$의 모든 땅의 높이를 $x$로 만들기 위해 필요한 병사의 수는 구간의 길이 $r-l+1 = W$, $i$번째 땅의 높이를 $h_i$라고 하면 다음과 같이 정리할 수 있습니다.

$$
\begin{aligned}
& (x-h_l)^2 + (x-h_{l+1})^2 + \cdots + (x-h_r)^2 \\
=\ & Wx^2 - 2(h_l + h_{l+1} + \cdots + h_r)x + (h_l^2 + h_{l+1}^2 + \cdots + h_r^2) \\
=\ & W\left[x - \frac{(h_l + h_{l+1} + \cdots + h_r)}{W}\right]^2 + \left(h_l^2 + h_{l+1}^2 + \cdots + h_r^2\right)W - \frac{\left(h_l + h_{l+1} + \cdots + h_r\right)^2}{W}
\end{aligned}
$$

위 식은 이차함수의 표준형이므로, $x = \frac{(h_l + h_{l+1} + \cdots + h_r)}{W}$인 경우에 최솟값
$$
\left(h_l^2 + h_{l+1}^2 + \cdots + h_r^2\right)W - \frac{(h_l + h_{l+1} + \cdots + h_r)^2}{W}
$$
를 가집니다. 
$h_l + h_{l+1} + \cdots + h_r$과 $h_l^2 + h_{l+1}^2 + \cdots + h_r^2$는 부분 합 알고리즘을 활용하여 계산할 수 있으므로, 생활관이 건설되는 구간 $[l, r]$이 정해지면 땅의 높이를 모두 동일하게 만들 때 필요한 병사의 수는 상수 시간 안에 구할 수 있습니다.

구간 $[l, r]$에서 동일한 $l$값에 대해 $r$값이 증가하면 반드시 필요한 병사의 수는 증가한다는 사실은 자명하므로, 투 포인터 알고리즘을 활용하면 모든 건물 건설 시작 지점 $l$에 대해 건설 가능한 최대 건물의 길이를 $x_l$이라고 하면, 쿼리로 입력되는 건설 가능 구간 $[l, r]$이 주어졌을 때 실제로 구해야 하는 값은 $l\le i\le r$에 대해 $\min(x_i, r-i+1)$입니다.

이때, $i + x_i$의 값은 항상 단조 증가함은 자명하므로, $x_k > r-k+1$이 되는 가장 작은 $k$에 대해 구간 $[l, k)$에서 $x_i$의 최댓값과 $r-k+1$중 최댓값을 출력해 주면 됩니다.
$x_k > r-k+1$이 되는 최소의 $k$는 이미 전처리해 둔 값을 바탕으로 이분 탐색으로 구할 수 있고, 구간 $[l, k)$에서 $x_i$의 최댓값은 segment tree등의 자료구조를 활용하여 구할 수 있습니다.