[codeforces] 1990D, 1988D, 1983D

1990D. Grid Puzzle (Difficulty : 1800)

문제 링크

풀이

첫번째 행부터 차례대로 살펴보면서 경우에 따라 다음과 같이 처리합니다.

Case 1. $a_{i} = 0$

이때는 특별한 처리 없이 넘어갑니다.

Case 2. $a_{i} > 2$

$i$번째 행을 전부 흰색으로 바꿉니다. 즉, $a_{i}$를 $0$으로 바꿉니다.

Case 3. $0 < a_{i} \leq 2$

$2 \times 2$ 크기의 그리드를 흰색으로 바꿉니다. 이때, $i$번째 행에서 제일 왼쪽에 있는 검정색 칸을 첫번째 행, 첫번째 열로 두어서 흰색으로 칠합니다.
$a_{i}$는 $0$으로, $a_{i+1}$은 흰색으로 칠하기 전에 $i$번째 행의 제일 왼쪽 칸이 검정색이면 $\max(0, a_{i+1} - 2)$로, 흰색이면 $\min(a_{i+1}, \max(2, a_{i+1} - 2))$로 바꿔줍니다.

위와 같이 처리하면서 연산을 수행한 횟수를 세면 됩니다. 시간복잡도는 $O(n)$입니다.

---

1988D. The Omnipotent Monster Killer (Difficulty : 2000)

문제 링크

풀이

이 문제를 다음과 같이 바꿔서 생각할 수 있습니다.

트리의 정점을 $c$가지의 색으로 칠합니다. 그리고 정점 $i$를 칠한 색을 $c_{i}$라고 한다면 $\displaystyle \sum_{i = 1}^{n} a_{i} \cdot c_{i}$의 최솟값을 구합니다.

이 문제는 DP를 사용해서 구할 수 있습니다. $DP[i][j]$를 $i$번째 정점을 $j$번 색으로 칠했을 때 $\displaystyle \sum_{v \in subtree_{i}} a_{v} \cdot c_{v}$의 최솟값으로 설정하고 트리 DP를 하면 됩니다.

하지만 $c$를 너무 큰 값으로 설정하면 TLE나 MLE를 받을 수 있습니다. 그래서 답을 구하기에 충분할 만큼만 $c$를 최대한 작게 잡아주는것이 필요합니다. 저는 색을 칠할 때 남아있는 정점의 최소 $\frac{1}{3}$을 칠해줘야 한다는 것을 보여주었고 $x \geq 32$이면 $300000 < 1.5^{x}$를 만족하므로 $c = 32$로 설정해서 문제를 해결했습니다.

하지만 $c$를 더 잡게 잡아줘도 AC를 받을 수 있었습니다. 그래서 에디토리얼을 참고해보니 $c = \lfloor \log_2{n} \rfloor + 1$로 잡아줘도 됐었고 그래서 $c = 19$로 잡아줘도 AC를 받을 수 있다고 합니다.

증명은 다음과 같습니다.

$f(i)$를 최솟값을 구하기 위해 $i$개의 색을 사용해야하는 경우 중에서 정점의 갯수가 가장 작은 트리의 정점의 갯수로 정의하면 다음이 성립합니다.

즉, $f(i) \geq 2^{i-1}$이 성립하고 그래서 $c = \lfloor \log_2{n} \rfloor + 1$만 잡아줘도 답을 구하는데 충분합니다.

참고로, 에디토리얼에 의하면 $c = 18$로 잡았을때의 반례가 존재한다고 합니다. 물론 저는 못찾을것 같긴하네요;;

시간 복잡도는 $O(nc^2)$입니다. 에디토리얼에서 언급한 내용을 적용하면 $O(n\log^{2}{n})$에 해결할 수 있습니다.

---

1983D. Swap Dilemma (Difficulty : 1700)

문제 링크

풀이

먼저 $a$와 $b$의 요소를 확인해서 한쪽에는 들어있지만 다른쪽에는 안 들어있는 값이 있는지 확인합니다. 있으면 당연히 불가능이고 없으면 아래로 넘어갑니다.

일단 $a$와 $b$에 적용되는 연산은 transposition이므로 parity가 서로 다르면 당연히 안됩니다.
그럼 같을 때는 어떨까요? 이 때는 무조건 가능합니다. 임의의 transposition은 $(i \, i+1)$ 형태의 transposition의 합성으로 바꿀 수 있습니다. 즉, $(i \, i+1)$의 합성 만으로도 $a$, $b$를 나타낼 수 있고 연산을 사용하여 차근 차근 하나씩 제거하면 됩니다. 다른 수열 하나가 먼저 끝난 경우 나머지 수열의 작업을 계속 수행하면서 이미 끝난 수열은 계속 똑같은 요소 두개를 골라서 왔다 갔다만 해주면 됩니다. 이렇게 되면 $a$와 $b$ 둘 다 오름차순으로 정렬되어 같아지게 됩니다.

즉, $a$와 $b$의 parity만 같은지 판별하면 됩니다.