Codeforces Round #729 (Div. 2)

바닥을 모르고 떨어지고 있다. 사실 이전 포스트 사이에 참여한 라운드가 좀 있지만 엄청나게 망하고 멘탈이 다 갈려버려서 후기도 못썼다. 정신 좀 차려보자.

 

A. Odd Set

길이가 2n인 수열에서 적절히 원소를 둘씩 짝지어 각 쌍들이 모두 홀수가 되도록 할 수 있는지 확인하는 문제. 두 자연수의 합이 홀수가 되려면, 홀수+짝수 형태야 한다. 따라서 수열 내에서 홀수의 개수와 짝수의 개수를 세서 같으면 Yes 다르면 No이다.

 

B. Plus and Multiply (업솔빙)

첫 번째 연산인 x * a는, 두 번째 연산 x + b로 치환될 수 있다. b = x*k (k는 자연수) 이라면 a = k+1인 x * a 연산과 동일하다. 따라서 첫 번째 연산을 적당히 하고 n까지 두 번째 연산을 적용하면 된다. 여기서 첫 번째 연산을 할 때마다 x가 a씩 증가하므로, 최대 log_a(n) 번 연산한다. 두 번째 연산도 모듈러를 통해 O(1)에 가능하다. 최종적으로 O(log n)에 가능하다.

첫 번째 연산과 두 번째 연산이 서로 치환될 수 있지 않을까 하는 경험에 근거한 의심을 금방 떠올렸지만 예시 입력을 잘못 계산하면서 모든게 꼬여버렸다.

 

C. Strange Function (업솔빙)

f(x)의 값을 고정하고 x가 어떤 수여야 하는지 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

• 어떤 x가 f(x) = 2이려면, 1의 배수이면서 2의 배수가 아니어야 한다. 즉, x | lcm(1) 이다.
• 어떤 x가 f(x) = 3이려면, 1의 배수이면서 2의 배수이면서 3의 배수가 아니어야 한다. 즉, x | lcm(1, 2) 이다.
• 어떤 x가 f(x) = 4이려면, 1의 배수이면서 2의 배수이면서 3의 배수이면서 4의 배수가 아니어야 한다. 즉, x | lcm(1, 2, 3) 이다.
• ...
• 어떤 x가 f(x) = k이려면, 1의 배수이면서 ... k-1의 배수이면서 k의 배수가 아니어야 한다. 즉, x | lcm(1, 2, ... , k-1) 이다.

따라서 n 이하의 수 중 f(x) = k인 수의 개수는 ⌊ n / lcm(1, ... , k-1) ⌋ 개이다.

한편, lcm(1, 2, ... , 37) > 1e16 이다. 따라서 37까지만 확인하면 된다.