[ABC254 Ex] Multiply or Divide by 2

https://atcoder.jp/contests/abc254/tasks/abc254_h
kenkoooo 레이팅: 2499
체감 난이도: P1
Tag: Greedy, Bitmask

---

$N$개의 수로 이루어진 두 multiset $A, B$가 주어진다. 다음 연산을 최소 횟수로 사용해서 $A$를 $B$와 같게 만들 수 있는지 구해야 하는 문제이다.

• $A$에 있는 원소 $n$을 고른다. 그 원소를 지우고, $A$에 $2n$을 추가한다.
• $A$에 있는 원소 $n$을 고른다. 그 원소를 지우고, $A$에 $\lfloor \frac{n}{2} \rfloor$를 추가한다.

---

본 대회 때는 풀지 못했던 문제이다. 접근의 큰 틀은 맞았으나, 세부적인 구현이 많이 꼬여 있었다. 다시 풀어보는데도 디버깅에 한 세월 쓴 거 봐서는 아마 시간이 좀 더 있었어도 못 풀었지 싶다.

 

주어지는 수들을 $2^a \times b$ 형태로 나타내어 보자. 여기서 $a$는 가능한 최댓값이다. $b$가 같은 수들끼리는 무조건 주어진 연산을 적용해서 상호 변환이 가능하다. 사용해야 하는 연산 횟수는 당연하게도 $a$의 차이이다.

$b$가 같은 수들끼리 변환을 하고자 할 때는, 가장 큰 수끼리 변환시켜주는 것이 최적이다. 따라서 각 $b$별로 우선순위 큐 같은 걸 사용해서 원소들을 관리하면 어렵지 않게 매칭을 시켜줄 수 있다.

 

나눗셈 연산을 한 번 사용하면 $a$가 $1$ 감소하고, $a$가 $0$인 경우에는 $b$가 절반으로 감소한다. $b$가 절반으로 감소하면 다시 새롭게 매칭이 일어날 수 있는 여지가 생기므로, $A$의 모든 원소가 $B$의 원소와 매칭될 때까지 이를 반복하면 된다. 주의할 점은 $b$는 감소하는 방향으로만 이동하기 때문에, Optimal한 성질을 만족하기 위해서는 $b$가 큰 것부터 매칭을 진행해야 한다. 시간복잡도는 $O(NlogNlogA)$ 이다.

 

https://atcoder.jp/contests/abc254/submissions/47753733