[Codeforces] Lyft Level 5 Challenge 2018 - Elimination Round

http://codeforces.com/contest/1033

 

A - King Escape (Code)

 

다행히 체스를 많이 해봤어서 퀸으로 갈라지는 사분면 내에 같이 위치하기만 하면 된다는 사실을 빨리 캐치했습니다. N이 그다지 크지 않아 Flood fill을 해도 됩니다.

 

B - Square Difference (Code)

 

$a^2 - b^2$ = $(a+b)(a-b)$이므로 a-b가 1이 아니면 절대 소수가 아니고, a-b가 1이면 a+b가 소수인지를 확인하면 됩니다.

 

C - Permutation Game (Code)

 

DP의 순서를 잘 정해줘야 합니다. $a[i]$가 큰 것 부터 처리를 하면 됩니다.

 

D - Divisors (Code)

 

약수가 3/4/5개인 수는 반드시 $p^2, p^3, p^4, pq$중 하나의 형태입니다. 주어진 수가 $p^2, p^3, p^4$일 경우는 binary search로 p를 찾아낼 수 있는데 $pq$일 경우에는 수가 많이 크기 때문에 인수분해가 쉽지 않습니다. 그렇기 때문에 $pq$ 형태의 수들을 전부 모은 뒤, 그들끼리의 최대공약수를 확인해 소인수를 최대한 뽑아내고, 이 과정에서 소인수분해가 불가능한 수들은 다른 수들에서 쓰이지 않는 유일한 소수 2개의 곱으로 이루어져있음을 알 수 있습니다.

 

D번에서 중복되는 수를 생각하지 못해 한 번 hack을 당하긴 했지만 그래도 굉장히 잘 풀렸네요.