Codeforces Round #781 (Div. 2)

문제풀기

lml 2022. 4. 15. 10:28

C번 정말 거의 다 했는데 결국 못 맞추고 D만 풀어서 예상 퍼포는 1697... 너무하네요

A. GCD vs LCM

-> (n - 3, 1, 1, 1)

B. Array Cloning Technique

-> 제일 많은 원소를 두 배로 늘리는게 최선

C. Tree Infection

문제를 잘못 읽어 처음에는 child가 아닌 subtree에 감염된 애가 있으면 감염이 가능하다고 착각하였다.

-> child의 수를 multiset에 넣어두고 매번 제일 감염되지 않은 child의 수가 많은 애의 child를 감염시키면 된다.

D. GCD Guess

첫 비트부터 차례대로 만들어나간다고 생각하자. (ans에 더해나간다 생각)

-> 처음으로 생각한 방법은 i번 비트를 확인할 때 (2^(i + 1) - ans, 2^(i + 2) - ans)로 확인할 수 있다.

-> 하지만 이럴 경우 a나 b가 2e9을 넘기는 경우가 존재한다.

-> 그래서 다시 생각해낸 것은 (2^i - ans, 3 * 2^i - ans) 를 넣어보면 된다.

E. MinimizOR

-> [L, R]의 모든 수를 넣어둔 Multiset S가 있다고 가정하자.

-> 이때 S[1]이 가진 최대의 비트보다 더 큰 비트를 가진 수들이 있다면 그대로 제거해주면 된다.

-> 그 다음에 S[1]의 최대 비트는 반드시 가져야 하는 비트이므로 모두 그 비트만큼 빼주면 된다.

-> 위의 과정을 반복하면 언젠가는 S[0] = S[1] = 0이 된다.

-> 딱히 시간내에 위 작업을 할 수 있는 아름다운 구현을 생각해내지 못하였다...

sol1)

-> 트라이를 통해서 위의 작업을 구현해줄 수 있다.

-> S[1]의 최대비트를 가진 숫자들의 개수는 무한정인 반면, 가지지 않을 수 있는 숫자는 오직 S[0] 뿐이다.

-> 따라서 S[1]의 최대 비트를 가진 수들에서 빼주는게 아니라, 가지지 않은 애한테만 그 비트를 더해준다.

-> 그렇다면 따로 저장하고 다녀야 하는 숫자는 오직 S[0]들 뿐이니 비트 개수인 30개 이하만 조작하면 된다.

비트 단위의 무언가를 만질 때 트라이를 생각해봅시다.

sol2) (editorial)

-> 과연 위의 과정에서 S의 모든 숫자들을 데려가야만 OR값을 최소화 시킬 수 있을까?

-> S[1]의 최대 비트가 k라면 최소의 k개 숫자만 고려하면 된다고 한다. (pf by 수귀)