Overview

Takeaway

[l, r] 구간에 1을 더하는 것을 정확히 $n$ 번 반복하여, 주어진 길이 $n$ 의 수열의 multiset과 같은 수열을 만들어낼 때, 사용된 구간의 길이의 최댓값을 최대화하는 문제이다.
최대 길이를 $c$ 라 두면, $sum-c \ge n-1$ , 따라서 $c \le sum-n+1$ 이어야 한다.
또한, $c$ 는 nonzero element의 개수보다도 적거나 같아야 하고, 따라서 둘 중 최솟값을 출력하면 된다.

Q 배열과 R 배열이 주어졌을 때, $x = yq_{i}+r_{j} \le K$ 인 $x,y$ 가 존재하면 $(q_{i}, r_{j})$ 를 배열에서 제거할 수 있다.
이때 가능한 최대 연산 횟수를 구하는 문제이다.
$r_{j} < y$ 이고, $x$ 가 작으면 좋으므로 최적의 $y$ 는 $r_{j}+1$ 이다. 따라서 $(r_{j}+1)q_{i}+r_{j} \le K$ 이면 두 원소를 제거할 수 있다.
고정된 $q$ 에 대해, $r \le \frac{K-q}{q+1}$ 이면 $r$ 을 사용할 수 있고, 이때 최대의 $r$ 을 사용하는 것이 유리하다.
$q$ 가 커질수록 우변은 작아지므로, 큰 $q$ 부터 가능한 최대 $r$ 을 사용하는 전략이 유효하다.

문제를 잘 변형하면, 구간 $m$ 개가 있고, 각 구간에 1이 적어도 하나는 등장하도록 길이 $n$ 의 binary string을 구성하는 경우의 수를 세는 문제가 된다.
Sol 1)
일단 쓸데없는 구간을 제거해서 정렬했을 때 구간의 양 끝이 단조 증가하도록 두자.
DP를 쓸 수 있을 것 같다. $dp(i)$ : $i$ 번째 구간부터 만족시키면서 채워갈 때의 경우의 수라 두자.
$i$ 번째 구간에서 최초로 등장하는 1의 위치에 따라 케이스워크를 할 수 있다. $O(N^{2})$ dp는 자명한데, 잘 생각해보면 펜윅 트리로 시간복잡도를 줄일 수 있는 꼴이다.
$dp(1) = (2^{d_1}-1)dp(2) + (2^{d_2}-1)dp(3) + \cdots + (2^{d_k}-1)2^(d_{k+1})dp(k+1)$ 과 같은 식이 나오는데, 마지막 항만 multiset으로 따로 처리해주면 된다.
Sol 2)
선형에 풀 수 있는 방법이 있다. 주어진 제약 조건을 다른 방식으로 변형하는 것이다.
구간 [l, r]에 1이 적어도 하나 존재한다는 것은, $r$ 이하의 $i$$a(i)=1$ 인 최대의 $i$ 가 $l$ 이상이라는 뜻이다.