CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)

Dashboard - CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

 

D 풀고 피곤해서 바로 런했는데 다행히 올랐다.

 

Prob. A

$a_1$을 고정하고 정렬한다.

 

Prob. B

전체의 0, 1 개수, 0, 1 각각의 최대 연속 개수를 계산한다.

 

Prob. C

$a_i=0$인 것을 모두 $1$로 바꿔주고 $b$의 상태를 확인한다. 이때 $b_i$가 모두 0 또는 1이면 가능하고, 각각 1번, 2번의 연산이 더 필요하다. 왜 되는지는 몰?루

 

Prob. D

간단한 식 정리를 해보면 $\frac{m}{a_{i+1}}$ 이하의 양의 정수 중 $\frac{a_i}{a_{i+1}}$와 서로소인 수의 개수를 $n-1$번 구하면 된다. $a_i$가 $a_{i+1}$의 배수가 아니라면 자명하게 불가능하다. 그런데 저걸 어떻게 구해야 할지 모르겠어서 구글링도 해보고 오일러 토션트 함수도 검색하면서 뇌절했다. 그러다 그냥 뚫어보자는 생각이 들어서, 폴라드 로를 써서 소인수분해하고 나이브하게 포함 배제를 해서 제출했더니 꽤 빠르게 맞아서 당황했다. 알고 보니 소인수분해를 해야 하는 수들의 곱이 크지 않아서 시복이 잘 보장되는 것이었다. 어렵지 않은 관찰이고, 설령 발견하지 못했더라도 요구하는 연산이 결코 쉽지 않다는 정수론적 직감에 의존해서 빠르게 풀었어야 하는데 아쉽다.