Codeforces Round #461 (Div. 2)

오늘부터는 참가한 codeforces의 풀이도 한 번 올려보려 한다. Round #461은 내가 부 계정으로 참가한 첫 대회였다. 나는 대회 끝까지 핵을 찾지 못한 A와, F를 제외한 B, C, D, E를 대회 시간 내에 풀었다.

#

A. Cloning Toys

Case-by-Case가 정해이다. 문제의 설명문의 조건이 이상해서, $(x, y) = (1, 0), (0, 1), (2, 1)$ 등의 찾기 힘든 핵이 많이 등장했다. 특히 $(2, 1)$ 케이스. 풀이는 다음과 같다.

i) $y=0$: 불가능하다.

ii) $y=1$: $x=0$인 경우에만 가능하다. $x>0$이어야 $x$를 클론하는 연산을 할 수 있기 때문이다...

iii) $y>1$: 초기 $(0, 1)$의 상태에서 무조건 $(x, y) \rightarrow (x+1, y+1), (x+2, y)$로만 갈 수 있기 때문에 ① $x$, $y$의 홀짝성이 다르고, ② $x+1 \ge y$ 이면 가능하다.

시간복잡도: $O(1)$

개인적으로는 이번 A와 같은 단순 hack 유도 문제를 정말로 싫어한다. 몇 가지 이상한 케이스들만 찾으면 E를 푼 것보다 많은 점수를 얻을 수 있다는 것이 너무나 불합리하다.

B. Magic Forest

문제 조건 $a \operatorname{xor} b \operatorname{xor} c = 0 \iff a \operatorname{xor} b = c$이기에, $a$, $b$에 대해서만 루프를 돌면서 $c$를 찾아주고, 조건에 맞는지 확인해준다.

시간복잡도: $O(n^2 )$

C. Cave Painting

얼핏 봐서는 $1$에서 $k$까지의 모든 modulo에 대해서 나누어야 할 것 같지만, 실제로 계산해야 하는 $k$는 훨씬 작아진다. $n$을 $1$에서 $k$까지의 모든 수로 나누었을 때의 나머지가 다르려면,

□ $1$로 나누었을 때의 나머지는, $0$만 가능하다.

□ $2$로 나누었을 때의 나머지는, $0$을 이미 썼기에, $1$만 가능하다.

□ $3$으로 나누었을 때의 나머지는, $0$, $1$을 이미 썼기에, $2$만 가능하다.

□ $\cdots$

□ $k$로 나누었을 때의 나머지는, $0$, $\cdots$, $k-2$를 이미 썼기에, $k-1$만 가능하다.

즉, $1$에서 $k$까지의 수로 나누었을 때의 나머지가 모두 다르려면, $n \ge \operatorname{lcm}(1, \cdots, k) - 1$여야 한다. $n=10^{18}$일 때 $k \le 37$이라고 한다. 정확한 수치를 몰라도 1부터 겹치는 나머지가 발견될 때까지 반복해 돌리면 최대 $i=37$에서 반복이 종료된다는 뜻이다.

시간복잡도: $f(n) := \operatorname{lcm}(1, \cdots, n)$일 때, $O\left(f^{-1} (n)\right)$. $f(x) \le x!$에서 $O({\log n\over\log\log n})$도 가능.

D. Robot Vacuum Cleaner

총 noise $=$ 조각 문자열 안의 noise $+$ 조각 문자열들 사이의 noise

왼쪽 항은 고정이므로, 오른쪽 항만 생각하자. 이 때 각 조각 문자열들의 s와 h의 개수만이 영향을 미친다. 조각 문자열들의 어떤 배열 $t_{a_1}, \cdots, t_{a_n}$이 최적이려면, 어떤 인접한 두 문자열을 바꾸어도 ($t_{a_1}, \cdots\, t_{a_{i+1}}, t_{a_i}, \cdots, t_{a_n}$으로 바꾼다) noise가 줄어들어야 한다. 역은 성립하지 않는다.

$t_i$ 안의 s의 개수를 $s_i$, h의 개수를 $h_i$라고 하면, $t_{a_i}, t_{a_{i+1}}$에서 $t_{a_{i+1}}, t_{a_i}$로 바꿀 때 증가하는 noise는 $s_{a_{i+1}} h_{a_i} - s_{a_i} h_{a_{i+1}}$이다.

$$s_{a_{i+1}} h_{a_i} - s_{a_i} h_{a_{i+1}}<0 \iff {h_{a_i} \over s_{a_i}} < {h_{a_{i+1}} \over s_{a_{i+1}}}$$

라는 것은, $h_i\over s_i$의 오름차순으로 $t_i$를 정렬하였을 때, 정렬된 순서가 아닌 배치라면, 인접한 두 문자열을 바꾸어서 noise를 증가시킬 수 있고, 따라서 최적이 아님을 의미한다. 정렬된 순서가 최적임은 직접적으로 증명하지 않았으나, 정렬되지 않은 모든 순서가 최적이 아님을 증명하였기에, 자명히 정렬된 순서가 최적이다.

따라서, $h_i\over s_i$의 오름차순으로 $t_i$를 정렬한 후 이어붙여, 왼쪽부터 차례대로 훑으며 noise를 계산하면 된다. 이어붙인 문자열의 각 h에 대해, 왼쪽에 있는 s의 개수를 합하면 계산 가능하다. 64비트 정수형을 써야 함에 유의하자.

시간 복잡도: $O( \sum l + n \log n )$

E. Birds

$dp(i, j)$ $:=$ $i$번째 나무까지 $j$마리의 새를 잡았을 때, 최대로 남길 수 있는 마나

로 정의하자. 만약 $j$마리의 새를 $i$번째 나무까지 잡을 수 없다고 할 때는, $dp(i, j) = -inf$로 정의하자. 이를 정의하지 않으면, 마나가 음수로 갔다가 다시 양수로 돌아오는 상태를 유효하다고 판단할 수도 있다. $dp(0, 0) = W$이 되고, 점화식은 다음과 같이 정의된다.

$$dp(i, j) = \max _ {j-c_i \le k \le j} \left( \min(dp(i-1, k) + X, W + Bk) - (j-k)\operatorname{cost}(i) \right)$$

이 식에서, $j$와는 무관하고 $i-1$, $k$와만 관련이 있는 식을 다음과 같이 분리해보자.

$$f(i, k) :=\min(dp(i, k) + X, W + Bk) + k\operatorname{cost}(i)$$

이렇게 $f$를 분리하면, $dp$의 점화식은 다음과 같이 간단하게 바뀐다.

$$dp(i, j) = \max _ {j-c_i \le k \le j} f(i-1, k) - j\operatorname{cost}(i)$$

이제, deque를 이용한 잘 알려진 슬라이딩 윈도우 기법으로 이를 최적화할 수 있다. 풀이는 $n$개의 phase로 이루어질 것인데, 각 phase에서는 $dp(i, *)$를 계산할 것이다. 각 phase는 # 이 문제에서 $a_k = f(i-1, k)$인 형태를 풀면 된다. 각 계산 단계에서 $dp(i, j)<0$이면 $dp(i, j) = -inf$를 처리해주는 것을 잊지 않도록 하자.

답은, $dp(n, k) \ge 0$인 최대의 $k$가 된다.

시간 복잡도: $O(n \sum c_i )$

F. Divisibility

공식 editorial에 따르면, well-guessing(야매)이 정해인 듯 하다. 전체집합 ${1, 2, \cdots, n}$에서 배수 관계인 쌍의 개수가 정확히 $k$개가 될 때까지 적절한 규칙으로 빼준다. 물론, 전체집합의 배수 쌍이 $k$개 미만이라면 무조건 불가능하다. 공식 풀이는 다음과 같이 하면 무조건 가능함을 주장하고 있다.

i) 쌍의 개수가 $k$개 이상이 유지되는 선 안에서, 맨 끝 수를 뺀다. $n$을 이 과정을 끝냈을 때의 전체집합의 크기로 재설정하자.

ii) 이 때, $n \over 2$ 이상의 수들만 적절히 빼도 무조건 $k$개인 해를 얻을 수 있다. 빼는 방식은 연결된 쌍의 수가 많은 것부터 빼던가 알아서 해도 된다.

증명은, $n$이 적절히 커지면 $n \over 2$ 이상의 소수 개수 $O({n \over \log n})$이 빼야 하는 쌍의 수인 $O(n^{1 over 3})$보다 많아진다는 사실로 대신한다고 한다. 그렇지 않은 예외 케이스 16개 모두 ii)의 방법으로 풀 수 있다고 한다.

시간 복잡도: $O(n \log n)$ 정도 (구현에 따라 다름)

풀이를 보고 나서도 찝찝한 문제이다.