[Codeforces] Round #505

http://codeforces.com/contest/1025

 

잘 친줄 알았는데 여러모로 아쉬운게 많았습니다.

 

A - Doggo Recoloring (Code)

 

N=1이면 Yes이고, N > 1이면, a to z에서 2개 이상 나온게 하나라도 있으면 Yes입니다. 아니면 No입니다.

 

B - Weakened Common Divisor (Code)

 

맨 처음엔 문제를 제대로 이해못했다가 이후에 깨달아서 맨 처음에는 lcm(a,b)의 gcd를 저장하고 있다가 그 값의 약수를 아무거나 출력했습니다. 이 때 굉장히 큰(2*10**9에 근접하는) 소수 2개가 들어오면 약수를 출력하는데 굉장히 오래 걸릴테니 각 a,b 값들로 먼저 나눠보는 작업을 했습니다. 그런데

2

6 6

4 9

에 대해 6을 답으로 출력해서 틀렸습니다. lcm을 취하면 안되고 문제에서 요구하는대로 정직하게 맨 처음에 들어온 a, b의 소인수를 전부 구해뒀다가 나중에 들어오는 a, b에 대해 계속 나눠보는 작업을 하기만 하면 됩니다. 여기서 hack을 10번이나 했습니다.

 

C - Plasticine zebra (Code)

 

주어진 연산은 잘 보면 그냥 해당하는 문자열을 마치 팔찌와 같이 원형으로 만든 다음 돌리는 작업입니다. 그렇기 때문에 주어진 문자열 S에 대해, S+S에서 bwbwbw...bw의 최대 길이를 찾고 출력하면 됩니다. 단 최대 길이가 S의 길이보다 길 경우 그냥 S의 길이를 출력하면 됩니다.

 

D - Recovering BST (Code)

 

맨 처음에는 D[i][j][r]을 i to j 구간에서 r을 root로 뒀을 때 가능한지로 두고 $O(N^4)$ 식을 구성했습니다. 실제로는 참조가 생각보다 덜 일어날테니 통과될 줄 알았는데 system test에서 터졌습니다. 대신 L[i][j]를 i to j 구간에서 j를 root로 두는 것이 가능한지, R[i][j]를 i to j 구간에서 i를 root로 두는 것이 가능한지로 두면 $O(N^3)$에 해결할 수 있습니다.

 

A/B/C/D를 빨리 풀어낸데다가 hack을 어마어마하게 많이 해서 점수가 많이 오를 줄 알았는데 B,D가 system test에서 터졌네요. 빠르게 코딩을 하는 것에 신경을 많이 쓰다 보니 나도 모르게 잘못된 가정을 하고 문제를 풀어내는 일이 종종 있는 것 같습니다. 신중하게 코딩을 해야겠습니다.