BOJ 28301 - 은하 온라인 마케팅 프로젝트

$a+t$가 $b$보다 작은 경우, $b,c$ 사이에 끼인 경우, $c$보다 커지는 경우를 각각 생각하면 된다.

여기서부터 어렵다.

우리가 어떤 도시 조합에 대해 $P$가 있을 때, $t$ 중 $f(t)$ 의 최소값이 나오게 되는 경우는 다음과 같이 두 개이다.

$P-s$ 라는 값에 주목해보면 이는 이 도시조합에서 $t$로 써야 하는 최소값이다.

$P-s \le c-a$ 라면 $t=\text{Min}(C, b-a)$ 일 때 $f(t)$의 최소가 나온다.

이는 $P \le c-a+s$ 일 때로 다시 표현할 수 있다.

두 번째로

$c-a < P-s \le C$ 인 상황은 $t=P-s$ 일 때 $f(t)$ 의 최소값이 나온다.

첫 번째 경우는 $a'$가 $c$ 를 넘지 않아도 될 때 최대한 $a'$ 를 $b$와 $c$ 사이에 넣어주는 방법이고, 두 번째 경우는 $a'=a+t$가 $c$를 넘기 때문에 최소로 추가해줘야 할 것만 추가해주는 방법이기 때문에 위와 같은 식이 도출된다.

결론적으로 어떤 도시 조합이 커버할 수 있는 $P$의 구간은 결국 $[s, s+C]$ 이기 때문에,

이 구간에 대해서 $f(t)$ 가 최소가 될 수 있는 구간은 다음과 같이 나뉜다.

$P$ 값을 $x$ 라고하고 최소 불균등도를 $y$라고 할 때,

식에서 위에것은 $x$와 관계없기 때문에 $P$ 를 내림차순으로 정렬하고 순회하며

$\text{Min}(s+C, c-a+s)$ 에 대해 어떤 도시조합 에서 $f(\text{Min}(C, b-a))$ 가 가능해졌다고 체크해주고 지금까지 사용가능해진 것 중 최소값을 정답으로 사용해주면 검사가 가능하다.

아래것은 그러지 못한다.

다음과 같은 관찰을 한다.

임의의 $P$값에서 $y$값이 $P-(c-a+s)+f(c-a)$ 이므로 $P$ 를 제외하고 봤을 때 어떤 가능한 도시 조합들 중 $c-a+s-f(c-a)$ 가 최대값이 되는 값을 선택해서 $P$ 에서 빼준 것이 최소가 된다.

이 값을 $K$ 라고 하면 $(c-a+s, K, +1)$ 과 $(s+C,K,-1)$ 처럼 이벤트를 구성하여 $P$ 를 오름차순으로 순회하며 현재 가능한 것들만 multiset 같은 곳에 넣어서 관리하는 방식으로 두 번째 정답 후보들을 순회할 수 있다.