BOJ 28301 - 은하 온라인 마케팅 프로젝트
중간까지는 관찰을 하고 그럴듯한 풀이를 짰지만 놓친게있었다.
다음 풀이는 에디토리얼을 공부하며 정리한 풀이이다.
어떤 정답이 되는 도시 조합은 도시들 중 가장 큰 값이 $a[i][j]$에 존재한다.
또한, 어떤 도시 조합에서 $t\ (0 \le t \le C)$ 명이 더 오는 이벤트를 열어야 하는 도시는 가장 작은 도시이다.
왜냐면 어차피 $t$ 값은 하나의 도시에만 이벤트를 열 수 있고, 가장 작은 도시에 이벤트를 열어야 최대 도시와 가장 작은 도시의 차가 줄어들 가능성이 가장 크기 때문이다.
따라서 처음에 $a[i]$ 를 모두 오름차순 정렬하고(중복도 제거해도 된다) 각 국가에서 가장 큰 도시들만 뽑아와서 도시 조합을 만들고,
거기서 가장 큰 값이 $c$라고 하면 $c$들을 모두 빼고 빼진 국가들은 그 다음 작은 $a[i][j]$ 값들을 넣어주는 것을 반복하고 이것이 불가능할 때 까지 반복하는 것으로 모든 도시 조합을 순회할 수 있다.
이제 이 도시 조합에서 가장 작은값을 $a$, 그 다음으로 작은 값을 $b$, 가장 큰 값을 $c$, 합을 $s$ 라고 하자.
$a$에 이벤트를 열어 $a'=a+t$ 라고 할 때, $t$ 가 뭐냐에 따라 가장 큰 도시와 가장 작은 도시의 차가 달라진다.
이 도시 조합에 $t$ 가 정해졌을 때 불균등도를 $f(t)$ 라 하면 다음과 같은 세 가지 상황이 나온다.
$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 같은 곳에 넣어서 관리하는 방식으로 두 번째 정답 후보들을 순회할 수 있다.
Comments