Codeforces Round #694 (Div. 2)

 

A. Strange Partition

수열과 정수 x가 주어진다. 수열의 원소들을 적절히 서로 합쳐서, 각 원소를 x로 나누고 올림한 값들의 총합이 최소가 되거나 최대가 되게 해야하는 문제.

어떤 수를 x로 나누고 올림했을 때 값이 바뀌려면 x로 나눈 나머지가 있어야 한다. 잘 생각해 보면 두 원소가 따로 있을 때는 x의 배수가 아니다가 합치면 x의 배수가 되어버릴 수 있다. 그러면 합치기 전에는 각각 올림해서 값이 증가할 텐데, 합친 뒤에는 나머지가 없기에 올림을 해도 값이 증가하지 않는다. 따라서 모든 원소를 다 합쳐버린 상태가 최소가 되는 상태이고, 전혀 합치지 않은 상태가 최대가 되는 상태이다.

 

B. Strange List

수열과 정수 x가 주어진다. 수열을 하나씩 순회하면서 지금 보는 원소가 x로 나누어지면, 그 몫을 x개 만큼 수열 맨 뒤에 추가한다. 만약 x로 나누어지지 않으면 끝낸다. 끝난 시점에서 수열의 총 합이 얼마인지 알아내는 문제.

일단 원소를 나눈 몫을 x개 추가하므로, 새로 추가되는 수들의 합은 원래 원소의 값과 같다. 즉, a_i/x를 x개 추가하므로 a_i/x * x = a_i 인 것이다. 새로 수열에 추가되는 연산이 최대 몇 번 있는지 생각해보면, 어떤 원소가 같은 수로 계속 나누어 떨어져야 한다. 입력되는 범위(<=10^9) 내에서 이런 경우는 2^29을 2로 나누는 경우일 것이다. 최대 29번 나누어지므로 각 원소당 29번 이내에 반복이 끝난다는 것을 알 수 있다. 따라서 그냥 주어진 수열에 끝나는 조건이 나올 때까지 x로 나눠나가다 보면 된다.

 

C. Strange Birthday Party

수열 k와 정렬된 수열 c가 주어진다. k의 모든 원소에 대하여 1. j<=k_i 를 만족하는 c_j 를 더하거나 2. c_{k_i}를 더할 수 있다. 단, 1번 방법에서는 c의 원소를 한 번씩만 사용할 수 있다. 합을 최소화하는 문제.

c가 정렬되어 있으므로 k_i가 클 수록 2번 방법을 선택했을 때의 페널티가 커진다. 따라서 k_i가 클 수록 가능한 1번 방법을 선택하는 것이 최적이라고 생각해 볼 수 있다. k를 내림차순으로 정렬하고, c_{k_i}의 합을 관리한다. 가장 큰 k_i부터 1번 방법으로 가장 작은 c_j를 선택해나가 보자. 적절히 합을 관리한다면 모든 경우를 확인할 수 있다.

 

D. Strange Definition (업솔빙)

두 수 x와 y에 대하여 lcm(x,y) / gcd(x,y) 가 완전제곱수면 '인접'했다고 정의해보자. 수열이 하나 주어지고 1초가 지날 때마다 서로 '인접'한 원소들이 서로 곱해진다. 쿼리로 시간이 주어졌을 때 각 쿼리에서 '인접'한 원소가 가장 많은 수를 알아내는 문제.

서로 '인접'한 원소들을 관리해주는 것이 키포인트이다. 어떤 원소를 소인수분해하면 a^3 * b^4 * c^5 이런 식으로 나올텐데 홀수 차수인 값만 남기고 무시해도 된다. 즉, a * c 이렇게 두 인자만 남게 된다. 왜냐하면 제곱수는 lcm(x,y) / gcd(x,y)한 후에 남아있어도 인접한 것은 자명하기 때문이다. 0초에서 1초로 넘어갈 때는 서로 곱해질 텐데, 이 경우도 마찬가지로 짝수차수가 만들어지면 무시하고 홀수 차수인 값만 남길 수 있다. 이렇게 되면 이전 상태에서 그대로 있거나 1로 바뀌게 된다. 1초에서 2초로 넘어갈 때는 이미 1초로 넘어올 때 정리가 되었기 때문에 '인접'한 관계가 변하지 않는다. 즉, 0초일 때 한번, 1초일 때 한번만 '인접'한 원소들의 수를 세어주면 된다.