8월 1주차 PS

컨셉은 쉬운 문제 밀기 + 그리디

 

Codeforces Round 703B. Eastern Exhibition

 

Sol) $x$축과 $y$축이 독립이기 때문에, 각각에 대해서 최소인 $x$좌표와 $y$좌표를 찾으면 충분하다.

이때, 거리가 절댓값들의 차의 합으로 정의되기 때문에 거리의 합의 함수가 아래로 볼록해진다.

따라서, 맨 밑의 계곡에 있는 원소의 개수를 찾으면 된다.

점 개수가 홀수일 때는 1, 짝수일 때는 중앙값 2개의 차이를 곱하면 답이다.

 

Codeforces Round 703D. Max Median

 

Sol) 

어떤 값의 최댓값을 묻고 있으므로, Parametric Search를 적용해서 답이 x보다 크거나 같은가?라는 질문으로 바꾼다.

어떤 구간에 주어진 값이 오직 1과 -1뿐이라고 하자. 그렇다면, 그 구간의 모든 수의 합이 0보다 크면 중앙값이 1이고, 작으면 -1임을 알 수 있다.

 

마찬가지 원리로 결정 문제를 푼다. x보다 작은 값들은 모두 -1, 그 반대는 1로 바꾼다. 이때 어떤 구간의 값의 총합이 0보다 크다면 그 구간에서의 중앙값은 x보다 크거나 같다. 

 

이제 길이 k 이상의 구간들의 합을 빠르게 구하는 방법을 찾아야 한다. 사실 여기서 중요한 것은 최댓값임을 알 수 있다. 여기서 점화식을 다음과 같이 정의하자:

 

$dp[i]$ : 1부터 $i$번째 숫자들 중 길이 $k$ 이상인 구간의 합의 최대

 

$s[i]$ : $[1, i]$ 구간의 부분합

 

$mn[i]$ : $[1, i]$ 구간에서 $s[n]$의 최소

 

이때 $dp[i] = s[i] - mn[i-k]$가 성립하며, 모든 배열을 $O(N)$에 계산 가능하다.

만약 dp[i]중 0보다 큰 값이 존재한다면 결정 문제의 답은 YES, 아니면 NO다.

 

따라서 결정 문제가 $O(N)$에 풀리고, 총 시간복잡도는 $O(NlogN)$이다.

 

Educational Codeforces Round 111B. Maximum Cost Deletion

 

Sol) 일단 $a$값은 아무래도 상관이 없다. 자른 길이에 비례하는 비용이기 때문에 끝나고 나면 항상 $an$만큼의 비용에 기여한다.

$b$만 중요한데, 만약 $b$가 양수라면 최대한 많이 자르는 것이 이득이므로 답은 $n(a+b)$

음수라면 최대한 적게 잘라야 한다. 결국 문제는 가장 적은 횟수로 문자열을 없애는 것으로 환원된다.

 

이 때 결국 중요한 것은 0, 1의 덩어리의 개수임을 알 수 있다. 즉, 모든 문자열을 01010..의 형태로 표현해도 상관이 없다.

몇 번 해보다 보면 1을 먼저 다 없애고 0을 없애거나, 0을 다 없애고 1을 없애는 것이 제일 이득임을 알 수 있다.

이는 exchange argument를 통해 증명 가능하다. (마지막 남은 뭉탱이로 보내면 이득임)

 

결론적으로 $b$가 음수일 때 답은 0, 1 덩어리 개수를 $m$이라고 할 때 $na+\lfloor{{{m}\over{2}}+1} \rfloor{}$이 된다.

 

BOJ 17082 쿼리와 쿼리

 

Sol) Exchange Argument를 살면서 처음 써본 문제입니다. 

 

1. 구간이 바뀌는 건 너무 어렵습니다. 그러니까 구간이 고정되어있다고 생각하고 한번 풀어봅시다.

포함되는 구간에 있는 숫자들을 전부 std::set에 집어넣습니다. 

그 뒤, 숫자가 바뀌면 크게 2가지 케이스가 있는데

 

i) 하나는 구간에 포함되어 있고, 다른 하나는 아닌 경우

ii) 둘 다 포함되거나 아닌 경우

 

i) 는 set에서 lower_bound를 때려서 $O(logN)$에 원하는 숫자를 찾아 지우고, 원하는 숫자를 찾아서 넣으면 됩니다.

ii) 는 답이 안 변하니까 완전 쉽습니다.

 

놀랍게도 이 시점에서 이미 $O(logN)$입니다. 즉, 구간을 정해주는 게 이 과정과 연관되어있다기보다는 그냥 독립적이라는 추측이 가능합니다.

 

2. 그리고 실제로 그러합니다. 숫자가 뭐든간에 왼쪽 주머니의 숫자와 오른쪽 주머니의 숫자를 작은 순서에서 큰 순서로 그대로 매칭시키는게 가장 유리합니다.

여기서 Exchange Argument를 적용합니다.

 

$L_i < L_j$, $R_i < R_j $라고 하겠습니다. 이때 $[L_i, R_i]$, $[L_j, R_j]$ 매칭과 $[L_i, R_j]$, $[L_j, R_i]$ 매칭을 생각해볼 수 있습니다. 각각 1번과 2번 매칭이라고 하겠습니다.

 

2번 매칭의 경우, 2번 매칭의 왼쪽 구간이 1번 매칭을 완벽히 포함합니다. 따라서, 2번 매칭을 포함하는 최적해가 존재한다면 그것을 1번 매칭으로 바꿔줘도 최적해입니다. 만약 1번 매칭에서 $L_i > R_i$ 또는  $L_j > R_j$ 가 성립해서 구간이 뒤집히는 일이 발생하면, 2번 매칭에서도 마찬가지 일이 발생합니다. 

 

 

결론적으로 항상 최적해인 매칭을 찾을 수 있으며,

이를 그대로 유지한 상태에서 1.의 논의를 사용하면 문제가 $O(M+QlogN)$에 풀립니다.

 

 

 

그리디 잘하고 싶다~~ 코포 블루 가고싶다~~