[Codeforces] Round #511 (Div. 1)

http://codeforces.com/contest/1034

 

문제 구성이 좀 많이 별로였습니다.

 

A - Enlarge GCD (Code)

$a_1, a_2, .. , a_n$에서 일부 수를 제거해 그들의 GCD를 $GCD(a_1,a_2,..a_n)$ 보다 크게 만들려고 할 때 최소한으로 제거해야 하는 수의 갯수를 묻는 문제였습니다. 문제는 괜찮았는데 설명을 이상하게 써놔서 문제를 이상하게 해석했습니다. 저만 그런게 아닌걸 보니 출제진의 잘못같네요. 아무튼, 이를 해결하기 위해서는 일단 $GCD(a_1,a_2,..a_n)$를 구한 후에 모든 수를 해당 값으로 나눕니다. 이제 $GCD(a_1,a_2,..a_n) = 1$이 되었습니다. 만약 $a_1,a_2,..a_n$이 전부 1이라면 답은 -1이 됩니다. 그렇지 않다면 각 수가 가지고 있는 map을 이용해 소수 인자의 갯수를 파악합니다. 해당 map에서 M[p]는 p로 나누어 떨어지는 수의 갯수를 의미합니다.

 

예를 들어 3 4 6 9 11이라고 한다면,

 

3에서 M[3]을 1 증가시켜주고

 

4에서 M[2]를 1 증가시켜주고

 

6에서 M[2], M[3]을 1 증가시켜주고

 

9에서 M[3]을 1 증가시켜주고

 

11에서 M[11]을 1 증가시켜줍니다.

 

최종적으로 M[2] = 2, M[3] = 3, M[11] = 1이므로 GCD가 3의 배수가 되게끔 하는 것이 가장 효율적임을 알 수 있습니다.

 

그런데, 15000000 아래의 소수는 대략 100만개로 각 수에 대해 100만개의 소수로 나눠보는 작업을 하면 TLE가 반드시 나게 되어있습니다. 대신에 sqrt(15000000)인 대략 4000 아래의 소수에 대해서만 나눠보고, 나누어떨어지지 않는 부분이 생기면 해당 수는 소수라고 처리를 하는 방식으로 시간 내에 통과할 수 있습니다. 문제는 좋았는데 해석이 좀 이상해서 아쉬웠네요.

 

B - Little C Loves 3 II (Code)

 

정말 마음에 안드는 문제입니다. N, M의 크기를 보아하니 규칙을 찾아야하는 문제인 것 같았고 계속 수많은 케이스를 머릿속으로 상상하며 노가다를 뛰었는데 별다른 느낌이 오지 않아 어쩔 수 없이 끝나기 20분 전쯤에 어떻게든 되겠지 하며 n,m이 둘 다 3이상이면 다 채울 수 있다고 가정하고(물론 n,m이 둘 다 홀수이면 한 칸은 못채운다고 가정하고), 어느 하나가 1이거나 2이면 노가다 뛴 결과로 끼워맞추도록 제출을 했는데 통과되었습니다.

 

min(n,m)이 5 이상일 때 open knight's tour가 항상 존재한다는 정리로 이 부분을 유도해낼 수 있다는 것을 대회가 끝나고 알게되었긴 하지만 문제가 마음에 들지는 않네요.

 

레이팅이 많이 올라서 좋긴 한데 그거랑 별개로 라운드 자체는 영 별로네요.