CodeForces Round 949 - Div 2

https://codeforces.com/contest/1981

 

 

Performance Rating : 2450

 

A

어차피 $2$로 나누는 것이 이득이기 때문에 $l$ 이상, $r$ 이하인 $2^n$ 중 가장 큰 수를 찾으면 되는데, 문제를 처음 보고 약수가 가장 많은 수를 찾는 것으로 착각하고 시간 손해를 조금 봤다.

 

B

결국 $low=\mathrm{max}(0, n-m)$, $hi=n+m$ 사이의 수를 모두 bitwise or 했을 때 값을 구하는 문제였다. $low$와 $hi$에서 처음으로 비트가 달라지면 그 아래의 비트들은 모두 1로 만들어진다는 것을 깨닫고 구현했다.

 

C

두 수의 가장 큰 비트를 맞춘 뒤 두 수가 같아질 때까지 2로 나누는 과정을 거쳐야 두 수 사이의 변환이 가능하다는 것을 생각했다. -1이 아닌 수들 중 바로 인접한 두 수 사이를 채울 수 있는지 판별하고, 변환의 횟수가 둘의 인덱스 차이에 비해 크거나 둘의 기우성이 맞지 않으면 바뀌는 것이 불가능하기 때문에 -1을 출력해 주었다. 채울 수 있다면 필요한 나누기, 곱하기 연산의 횟수를 계산해 주고 횟수에 맞춰 0이 되지 않도록 연산을 진행했다.

 

D

우선 수의 종류 수가 $x$개라 했을 때 최대 길이를 생각해 보았다. 최대 길이는 $x(x+1)/2+1$이다. 길이가 $x(x+1)/2+1$보다 크면 $a_i*a_{i+1}$의 개수가 $x(x+1)/2$개보다 많기 때문에 비둘기집 원리에 의해 같은 숫자가 나올 수밖에 없기 때문이다. 두 번째로 $x$개가 있을 때 길이를 $x(x+1)/2+1$로 만들 수 있는지를 생각해 보았다. 이는 노드의 수가 $x$개인 완전 그래프에서 오일러 회로가 존재해야 하는데, $x$가 홀수면 가능하지만, $x$가 짝수이면 $x(x+1)/2-x/2+1$개의 간선이 최대였다. 그러므로 $x$의 값을 구해놓고 $x$의 기우성에 따라 오일러 회로를 만드는 풀이를 작성했다. $a_ia_j=a_pa_q$인 경우가 없도록 하기 위해 $a_i$를 모두 서로 다른 소수로 설정해 두었다.

 

E

$a_i$ 기준으로 정렬해 두고 풀 생각을 했으나 시간 복잡도를 $O(n^2)$ 아래로 줄이지 못했다. jiangly님의 코드를 보니 $a_i$ 기준으로 정렬되어 있는 set과 스위핑을 활용해 간선의 개수를 획기적으로 줄일 수 있다는 것을 알게 되었다.