$x$ 이하인 실수의 개수를 $f(x)$라고 하면, 식은 충분히 작은 $\varepsilon$에 대해 $\left\lvert\frac{f(R) - F(L-\varepsilon)}{N} - (R - L)\right\rvert$ $= \left\lvert\left(\frac{f(R)}{N} - R\right) - \left(\frac{f(L-\epsilon)}{N} - \left(L - \epsilon\right)\right) + \epsilon\right\rvert$이 가질 수 있는 값의 상한을 구하는 문제가 됩니다. 여기서 $\epsilon$은 충분히 작으니까 무시할 수 있기 때문에, $\frac{f(x)}{N} - x$이 가지는 값의 상한과 하한의 차이를 구하는 문제가 됩니다.

$N$개의 수를 정렬해서 $A_1, \cdots, A_{N}$이라고 합시다(편의상 $A_0 = 0, A_1 =1 + \varepsilon$이라고 가정합니다). $A_i \le x < A_{i+1}$인 $x$에 대해 $\frac{f(x)}{N} - x$는 $\frac{i}{N} - A_i$부터 $\frac{i}{N} - A_{i+1}$ 미만까지의 값을 가집니다.

즉, 이 값들의 최솟값과 최댓값을 계산해서 그 차이를 출력해주면 됩니다.

동적 계획법 배열 $D_{i,\ j}$를 게임을 $A_i, \cdots, A_j$에서 진행했을 때 답이라고 합시다. $A$가 $k$번째 수를 가져가면, $B$는 왼쪽과 오른쪽 중 이후 게임에서 고른 정수의 합이 작은 쪽을 고를 것입니다.

$D_{i,\ j} = \left( \max_{i \le k \le j} \min(D_{i,\ k-1 }; D_{k+1,\ j}) + A_k \right)$ 이고, 이를 직접 계산하면 $\mathcal{O}(N^3)$이 됩니다.

이제 다음과 같은 관찰을 합시다.

• $D_{i,\ j} \le D_{i,\ j+1}; D_{i,\ j} \le D_{i-1,\ j}$
  • 가져갈 수 있는 정수가 더 늘어났으므로, $A$가 가져간 정수의 합은 증가합니다.
• $k \le K_{i,\ j}$에 대해서는 $D_{i,\ k-1} < D_{k+1,\ j}$이고, $k > K_{i,\ j}$에 대해서는 $D_{i,\ k-1} \ge D_{k+1,\ j}$인 $K_{i,\ j}$가 존재합니다.
  • $D_{i, k-1}$은 $k$가 증가함에 따라 단조증가하고, $D_{k+1, j}$는 $k$가 증가함에 따라 단조감소하기 때문입니다.
• $K_{i-1,\ j} \le K_{i,\ j} \le K_{i,\ j+1}$
  • $k > K_{i,\ j}$에 대해 $D_{i-1,\ k-1} \ge D_{i,\ k-1} \ge D_{k+1,\ j}$이므로, $K_{i-1,\ j} \le K_{i,\ j}$입니다.
  • $k \le K_{i, j}$에 대해 $D_{i,\ k-1} < D_{k+1,\ j} < D_{k+1,\ j+1}$이므로, $K_{i,\ j} \le K_{i,\ j+1}$입니다.

이제 식을 $K_{i,\ j}$를 기준으로 다시 쓸 수 있습니다.

• $K_{i,\ j}$는 $K_{i-1,\ j}$ 이상 $K_{i,\ j-1}$ 이하에서 차례대로 탐색해서 찾습니다.
• $B$가 왼쪽을 남기는 경우, $L_{i, j} = \max_{i \le k \le j} (D_{i,\ k-1 }+ A_k) = \max(L_{i,\ j-1}; D_{i,\ j-1} + A_j)$입니다.
• $B$가 오른쪽을 남기는 경우, $R_{i, j} = \max_{i \le k \le j} (A_k + D_{k+1,\ j}) = \max( R_{i+1, \ j}, A_i + D_{i+1, \ j } )$입니다.
• $D_{i, \ j} =\max(L_{i,\ K_{i, \ j}}, R_{K_{i, \ j} + 1,\ j })$이고 $K_{i, j}$를 기준으로 왼쪽 혹은 오른쪽을 가져갑니다.

$K_{i,\ j}$를 탐색하는데 걸리는 시간은 $K_{i,\ j-1} - K_{i-1,\ j}$에 비례합니다. 이를 모든 $(i, j)$에 대해 더하면 $\mathcal{O}(N^2)$이됩니다($i-j$가 같은 것끼리 묶으면 항이 상쇄되어서 $\mathcal{O}(N)$입니다.)

$K$등분 문제의 풀이를 생각 해봅시다. 전체의 합을 $S$라고 하면 $i$번째 구간까지의 누적합은 $\frac{iS}{K}$가 되어야 합니다. 결국 누적합을 구한 이후 $\left(\frac{S}{K}, \frac{2S}{K}, \cdots, \frac{(K-1)S}{K}\right)$가 부분수열로 등장하는 경우의 수를 세는 문제입니다.

편의상 $K\ne 0$인 경우만 생각하고, $K=S$라고 생각합시다. 이러면 $(1, 2, \cdots, K-1)$가 부분수열로 등장하는 경우의 수를 세는 문제가 됩니다. $i$번째 수인 $A_i$로 끝나는 부분수열의 경우의 수를 $D_i$라고 하면 $D_i = \sum_{j < i;\ A_j = A_i+1} D_j$가 됩니다. 이후 $A_i = K-1$인 $i$에 대해 $D_i$를 모두 더하면 답이 됩니다.

답이 $x$인 수열이 있고, 이를 $K$등분 해야한다고 생각합시다. 이제 $K$를 $1$ 증가시키고 $K$를 삽입해 봅시다. 가장 처음으로 등장하는 $K-1$뒤에 $K$를 삽입하면, 두 수의 $D_i$ 값은 같을 것입니다. 또한 가장 뒤에 $K$를 삽입하면, 이에 해당하는 $D_i$값은 $x$일 것입니다. $A_i = K-1, D_i = 1$인 $i$가 있고, 전체 답이 $x$인 수열을 $ax+b$로 바꾸는 방법은 다음과 같습니다.

• 처음으로 등장하는 $K-1$ 뒤에 $K$를 $b$개 삽입합니다.
• 마지막에 $K$를 $a$개 삽입합니다.

여기서 주목할 점은 이를 반복적으로 사용하기 위해서는 항상 $b \ge 1$이어야 하고, 수가 $a+b$개가 늘어난다는 것입니다. $a=2, b=1; a=2, b=2$를 사용하면 답을 $2$배씩 늘릴 때 마다 수가 최대 $4$개 늘어나므로, $240$개 정도로 문제를 해결할 수 있습니다.

더 효율적인 방법은 $a=4, b=1; a=4, b=2$를 함께 사용해서 $4x+1$ 혹은 $4x+2$꼴의 수의 경우에는 $a=4$를 사용하는 것입니다. 이제 $K \ge 1$에 대해 다음 사실을 증명합시다.

• 답으로 $2^K$ 이하의 수를 만들 때, 홀수는 $3K-2$, 짝수는 $3K-1$개 이하의 수를 사용하는 것이 가능합니다.
  • $K = 1, 2, 3$일 때: $x$를 만들기 위해 $1$을 $x$개 쓰면 됩니다.
  • $K > 3$일 때, $x \le 2^K$라고 합시다.
    • $x = 4k+1$: $k$를 만드는 데에 $3(K-2)-1$개 이하의 수를 사용합니다. $3(K-2)-1 + (4+1) = 3K-2$입니다.
    • $x=4k+2$: $k$를 만드는 데에 $3(K-2)-1$개 이하의 수를 사용합니다. $3(K-2)-1+(4+1) = 3K-1$입니다.
    • $x=4k+3 = 2(2k+1)+1$: $2k+1$을 만드는 데에 $3(K-1)-2$개 이하의 수를 사용합니다. $3(K-1) -2 + (2 + 1) = 3K-2$입니다.
    • $x = 4k+3 = 2(2k+1)+2$: $2k+1$을 만드는 데에 $3(K-1)-2$개 이하의 수를 사용합니다. $3(K-1)-2 + (2+2) = 3K-1$입니다.

이렇기에 우리는 $10^{18} \le 2^{60}$이하의 수를 $179$개 이하의 누적합을 써서 만들 수 있고, 원래 문제인 변화값은 $180$개 이하로 사용해서 만드는 것이 가능합니다.

이 방법을 발전 시켜서 $170$개 이하만 사용해서 답을 만드는 것도 가능합니다. 몇 가지 $a$에 대해 시도해 본 결과중 최솟값을 동적 계획법 등으로 관리하면, 더 적은 개수로 답을 만들 수 있습니다.

$A_{i-1} \le A_i \ge A_{i+1}$을 만족하는 $i$를 아름다운 위치라고 합시다.

아름답지 않은 위치를 $i_1, i_2, \cdots, i_m$이라고 하고, $i_0 = 0, i_{m+1} = N+1$이라고 합시다. 아름다운 수인 $i_k+1$부터 $i_{k+1}-1$번째 까지 수가 만족해야 하는 조건은 $A_{i_k} \le A_{i_k+1} = A_{i_k+2} = \cdots = A_{i_{k+1}-1} \ge A_{i_{k+1}}$라는 것을 알 수 있습니다.

아름다움을 최대화하기 위해서는 $m$이 가능한 한 작아야 합니다. 아름답지 않은 위치의 개수가 $m$개인 해당하는 수열을 만들기 위해서는

• $N$개의 수 중 $m$개의 수 $V_1, V_2, \cdots, V_m$을 고릅니다.
• 나머지 수의 종류가 $m+1$개 이하입니다.
• 각 수는 $V_1$ 이상의 수, $\max(V_1, V_2)$ 이상의 수, $\max(V_2, V_3)$ 이상의 수, $\cdots$, $\max(V_{m-1}, V_m)$ 이상의 수, $V_{m}$ 이상의 수여야 합니다.

여기서 다음 관찰을 합시다.

• 수의 범위를 최대한 늘리기 위해서는 $V_1, V_2, \cdots, V_m$이 정렬되어있어야 합니다.
  • $V_1, \max(V_1, V_2), \cdots, \max(V_{m-1}, V_m), V_m$중 $V_i$ 이상인 수는 $i+1$개 이상입니다. 이를 정확히 $i+1$개로 만드는 방법은 $V_1 \le V_2 \le \cdots \le V_m$으로 나누는 것입니다.
• 마찬가지로, 나머지 수 역시 정렬되어 있어야 합니다. 나머지 수는 $V_1, V_2, \cdots, V_{m-1}$이상이 1개씩, $V_{m+1}$ 이상이 2개 있어야 합니다.

그래서 우리는 수를 묶어서 작은 것부터 하나씩 추가할 것입니다. 그 후 조건에 맞지 않을 때 즉, $m$을 늘려야 할 때마다 $m$을 하나씩 고를 것입니다. 남은 수의 서로 다른 수의 개수가 가장 작아야 하기 때문에, 제일 적게 남은 수로 $V_m$을 사용합니다. 수가 작은것부터 추가되기 때문에 이후에 추가되는 수는 모두 $V_m$이상이고, 기타 수의 조건에 영향을 주지 않습니다. 구현은 우선 순위 큐 등을 사용해서 $\mathcal{O}(N \log N)$ 시간에 가능합니다.

오차가 $\varepsilon$ 이하인 함수 $f(x)$와 $g(x)$에 대해, $\left(\frac{f+g}{2}\right)(x)$의 오차도 $\varepsilon$이하입니다. $f$의 등고선이 볼록이기 때문에 $f$에 따른 오차는 Unimodal하고 삼분탐색을 사용할 수 있습니다. 주어진 절대오차 및 상대 오차 허용값을 $\varepsilon$, 좌표 범위를 $L$이라고 하면 $2$차항과 $1$차항에 대한 삼분탐색을 차례로 사용해서, $\mathcal{O}(N \log^2 \left(\frac{L}{\varepsilon}\right))$ 정도의 시간에 문제를 해결할 수 있습니다($2$차항과 $1$차항이 주어지면, 상수항은 $2$차항과 $1$차항만 계산한 값과 $y$값 차이의 최솟값과 최댓값의 평균으로 설정하면 됩니다.)

이제 (계산시의) 오차에 대해 생각해 봅시다. Machine epislon을 $\epsilon$이라고 합시다. 함수를 $f(x) = ax^2+bx+c$와 같이 잡으면, 해당하는 $c$의 값이 $\mathcal{O}(L^2)$정도까지 발산할 수 있기 때문에, $\mathcal{O}(L^2\epsilon) << \varepsilon$여야 하고, $\epsilon << 10^{-18}$이어야 하기 때문에, long double 자료형을 사용해야 하며, 이를 사용해도 실수 오차 문제가 발생할 수 있습니다. 그래서 다음과 같은 형태의 함수를 생각해봅시다.

• 가능한 $x$의 범위가 $[l, r]$일 때, $f(x) = a(x-l)(x-r) + b(x-l) + c$꼴입니다.

이제 최적인 $f$에 대해 각 항이 $\mathcal{O}(L)$로 bound됨을 보입시다.

• 오차의 제곱근은 $L$ 이하입니다
  • $f(x) = 0$의 경우 오차의 제곱근은 좌표 범위인 $L$ 이하가 됩니다.
• $\lvert c \rvert$는 $2L$이하입니다.
  • $f(l) = c$이므로, $\lvert c \rvert = \lvert f(l) \rvert \le L + \lvert y_i \rvert \le 2L$입니다.
• $\lvert b(x-l) \rvert $은 모든 $x$에 대해 $4L$이하입니다.
  • $f(r) = b(r-l) + c$이므로, $\lvert b(x-l) \rvert \le \lvert b(r-l) \rvert \le L + \lvert y-c \rvert \le L + \lvert y \rvert + \lvert c \rvert \le 4L$입니다.
• $\lvert a(x-l)(x-r) \rvert$는 모든 $x$에 대해 $8L$이하입니다.
  • $\lvert a(x-l)(x-r) \rvert \le \lvert f(x) - b(x-l) + c \rvert \le y + \lvert f(x) \rvert + \lvert b(x-l) \rvert + \lvert c \rvert \le 8L$ 입니다.

그러므로 해당 $a, b, c$를 사용해서 삼분탐색을 하면, $\mathcal{O}(L \epsilon) << \varepsilon$이면 충분하고, $\epsilon << 10^{-12}$ 정도이므로 double 자료형만 사용해도 문제를 해결할 수 있습니다.

연산을 수열 전체에 사용한다고 생각하면 사용해야하는 연산의 횟수는 $\max(K - \min A, 0)$이다. 이 이하로 사용해서는 최솟값을 $K$ 이상으로 만들 수 없다. 이제 가능한 총 비용의 최솟값을 구하자.

이전 관찰로, 우리는 연산을 수열의 최솟값에 해당하는 인덱스에만 증가시켜주면 된다는 것을 알 수 있다(최솟값이 늘어나면, 필요한 횟수가 줄어든다.) 그렇기에 최솟값에 해당하는 모든 인덱스를 포함하는 가장 짧은 구간에 연산을 사용하면 된다는 것을 알 수 있다. 이를 그대로 구현하면 $O((\max A) \times N)$ 정도의 시간이 든다.

원래 최솟값이었던 수는 항상 연산에 포함되어있다는 사실을 주목하자. 각 인덱스가 증가되는 횟수는 이 값을 최대로 해서 바깥으로 갈수록 줄어드는 모양이라는 것을 알 수 있다(연산의 구간이 연속되어있다.) 이를 이용해서 각 인덱스가 증가되는 횟수를, 자기 이전 혹은 이후 인덱스가 증가되는 횟수에 따라 계산해주면 된다. 시간 복잡도는 $O(N)$ 이다.

수가 같은 $4$개의 인덱스 $a < b < c < d$가 존재하고, 제거 연산이 $(a, d) \rightarrow (b, c)$순이 아니면, 제거 연산을 $(a, d) \rightarrow (b, c)$순으로 바꾸어 주는 것으로 더 높은 점수를 얻을 수 있다. 이를 통해, 우리는 같은 수에서 제거되는 쌍을 바깥쪽부터 차례로 만드는 것이 가장 이득이라는 것을 알 수 있다.

네 인덱스 $a < b < c < d$에 대해, $(a, c)$와 $(b, d)$는 어느것을 먼저 수행해도 상관 없고, $(a, d)$와 $(b, c)$는 $(a, d)$의 제거 연산을 먼저 수행하는 것이 이득이라는 것을 알 수 있다. 이를 통해, 우리는 정해진 쌍을 제거하는 연산을 두 인덱스 차이 순서대로 실행하면, 가능한 최고의 점수를 얻는다는 것을 알 수 있다.

이를 세그먼트 트리 등을 이용하여 시뮬레이션하면, 시간복잡도는 $O(N \log N)$이다.

$D[a][k][c]$를 현재 $a$ 정점에 있고, $k$번 스킵할 수 있으며, 다음 간선의 문자가 $c$일때 가능한 최대 길이라고 정의하자.

다음 문자를 스킵하는 경우와 경우하지 않는 경우의 두 가지가 있다.

• 문자가 일치하는 경우: $a \xrightarrow{c} b$에 대해서 $1+D[b][k][next(c)]$, $next(c): c$의 다음 문자
• 문자가 일치하지 않는 경우 :$a \xrightarrow{c} b$에 대해서 $D[b][k-1][c]$. $(k > 0)$

현재 위치에서 끝낼수 있으므로, 0과 위 값들의 최댓값을 구하면 된다.

이를 동적계획법을 사용하여 해결하면 되는데, 정의가 순환적이라는 문제가 생긴다. 즉 이전 방문한 DP상태를 다음에도 방문할 수 있다는 의미이다. 이를 위해서 DP를 순서대로 돌리는 것이 아니라, memoization을 활용하고, 다음과 같은 방법으로 처리한다.

• 현재 상태를 방문한 적이 없는 경우, 위 DP식을 이용해 답을 찾는다.
• 현재 상태에서 정답을 찾은 적이 있을경우, 기존에 저장한 해당 정답을 반환한다.
• 현재 상태에서 정답을 찾은 적이 없는데 이전에 방문한 적이 있는 경우, 현재 상태에서 다시 정답으로 돌아오는 방법이 있다는 의미이다. 이 경우에는 방문 횟수가 무한할 수 있다.

$k = 0, 1, 2$일 때는 방문 횟수가 무한하면 문자열의 길이가 무한하지만, $k=-1$일 때는 문자열의 길이가 무한하지 않을 수 있다(가령이면, $A, B$가 있는 사이클을 무한히 반복한다.) 이를 처리하는 방법은 다양한 방법이 있는데 하나는 SCC를 구해서 정점을 압축하는 방식이다. 다른 방법은 방문한 사이클이 유효하게 문자를 붙여오면서 한바퀴를 돌았는지를 판단하는 방법이 있다. 뒤의 방법을 조금 더 설명한다.

문자를 붙일 때마다(즉, 1번 경우만) 깊이가 $1$씩 깊어지도록 코드를 작성하면 같은 상태를 다시 방문했을 때 깊이가 깊어졌으면 문자를 붙이는 사이클이 존재하므로 답은 무한하다. 그렇지 않으면, "사이클은 존재하지만, 해당 사이클을 방문하면서 문자를 붙일수 없는 상태"이기 때문에, 답을 현재 상태에서 갱신하지 않는다(즉, 0을 반환한다.)

이와 같이 구현하면 시간복잡도는 $k$가 유한할 때 $O(kM)$이 된다. $k = \infty$ 일 때는 $k$가 가질 수 있는 상태가 $\infty$ 하나로 유일하기 때문에 시간복잡도가 $O(M)$이다.

어떤 직사각형이 꽉 찬 직사각형인지 판단하는 법을 생각해보자. 우리가 직사각형 내부 칸의 최솟값과 최댓값을 안다면 직사각형 안에는 최솟값부터 최댓값까지 모든 수가 다 존재해야 한다. 즉, 최댓값에서 최솟값을 뺀 값에 $1$을 더한 값이 면적과 같은지 확인하면 된다.

이제 직사각형의 최솟값 $T$를 고정시켜보자. 해당 수만 포함하는 직사각형은 자명하게 꽉 찬 직사각형이다. 이제 다음으로 큰 꽉 찬 직사각형을 구해보자. 이 꽉 찬 직사각형은 상하좌우중 한 방향으로 늘어나야한다. 이 중 "늘어나는 영역의 최솟값과 최댓값"에 대해 살펴보자.

• 늘어나는 영역의 최솟값이 $T$이하이면 해당 영역을 포함하면 직사각형의 최솟값이 $T$가 아니기 때문에 해당 방향으로 늘어나날 수 없다.
• 늘어나는 영역의 최댓값중 가장 작은 값 $C$쪽으로는 항상 늘어나야 한다. 다른 방향으로만 늘이게 되면 최댓값은 $C$보다 큰데 $C$를 포함하지 않게 된다.

각 수에 대해 직사각형 영역은 $2N-1$번 늘어나므로, 총 $2N^3-N^2$번 미만 늘어난다. $O(N^3)$에 전처리를 해서 늘어나는 구간에 대한 정보를 $O(1)$에 계산할 수 있으면, 시간복잡도 $O(N^3)$에 문제를 풀 수 있다.

일단, $P^k E_k$를 구하는 식을 써보자. 카드 종류 개수의 기댓값은 기댓값의 선형성을 이용하면 $1$번 카드가 뽑힐 확률 + $2$번 카드가 뽑일 확률 + $\cdots$ + $N$번 카드가 뽑힐 확률로 계산할 수 있다. 여사건인 $i$번 카드가 $k$번 중에 한 번도 뽑히지 않을 확률은 $\left(\frac{P-p_i}{P}\right)^k$이므로 $i$번 카드가 뽑힐 확률은 $1-\left(\frac{P-p_i}{P}\right)^k$이다. $P^k E_k$는 이를 $i = 1, \cdots, N$에 대해 더한 $\sum_{i=1}^N P^k - (P-p_i)^k$와 같이 계산할 수 있다. 이를 직접 계산하면 $O(NK)$가 된다.

이제 시간복잡도를 줄여보자. 위 식을 정리하면 $N P^k - \sum_{i=1}^N q_i^k$ $(q_i = P-p_i)$가 된다. $F_k = \sum_{i=1}^N q_i^k$을 모든 $i = 1, \cdots, K$에 대해 빠르게 구해야 한다. 생성함수 $f(x) = \sum_{k=0}^{\infty} F_k x^k$를 생각하자. $f(x) = \sum_{k=0}^{\infty} \left( \left( \sum_{i=1}^N q_i^k \right) x^k \right) = \sum_{i=1}^N \left( \sum_{k=0}^{\infty} \left( (q_i x)^k \right) \right) = \sum_{i=1}^N \frac{1}{1-q_i x}$가 된다.

$\sum_{i=1}^N \frac{1}{1-q_i x}$을 분수형태로 구하는 법은, 좌우 절반으로 나눠서 왼쪽이 $\frac{A(x)}{B(x)}$, 오른쪽이 $\frac{C(x)}{D(x)}$일  때 $\frac{A(x)D(x) + B(x)C(x)}{B(x)D(x)}$로 구하면 되고, 다항식 곱셈을 세 번 사용하면 된다. 이를 구하는 시간복잡도는 $T(N) = 2T(N/2) + O(N \log N)$이고, $T(N) = O(N \log^2 N)$이다.

이제, $\frac{A(x)}{B(x)}$와 같은 식을 실제로 계산해야 하는데, 다항식 나눗셈을 사용하면 이 값을 $K$번째 항까지 $O(K \log K)$에 계산할 수 있다. $f(x)$의 각 항을 구할 수 있으니, 각 $F_k$를 알 수 있다.

시간복잡도는 $O(N \log^2 N + K \log K)$이다.