[Codeforces] Round #517 Div. 1

http://codeforces.com/contest/1071

 

A - Cram Time (Code)

 

$k(k+1)/2 <= a+b$인 k를 찾고 나면 n+m은 최대 k임은 자명합니다. 이제 1부터 k까지의 수를 적절하게 p와 q에 분배만 하면 되고, k부터 1까지 보면서 해당 값이 a 이하여서 p에 줄 수 있으면 p에 준 후 a를 해당 값만큼 감소시키고, 불가능하면 q에 주면 됩니다.

 

B - Minimum Path (Code)

 

x좌표+y좌표 = k인 모든 점들은(ex : (0,k),(1,k-1) , .. ) 반드시 Path에서 방문 시점이 동일합니다. 그러면 이제 첫 번째로 a가 최대 어느 대각선까지 이어질 수 있는지를 확인합니다. 이는 $D[x][y] = $(0,0)부터 해당 경로까지 이어지는 a의 최대 갯수를 구함으로서 해결할 수 있습니다.

 

그 후로는 x좌표+y좌표가 같은 대각선 상의 점들에 대해 radix sort와 비슷한 느낌으로 최대한 작은 알파벳을 밟도록 처리를 해나가며 끝점에 도달하면 됩니다.

 

A, B를 신기할정도로 빨리 풀었고, D도 보자마자 풀이에 착안해 열심히 짰는데, 아쉽게도 풀이에 살짝 오류가 있었고 이를 해결하지 못한 채로 대회가 끝났습니다. 만약 D도 풀어냈다면 한 방에 레드에 진입할 수도 있을 뻔 했네요. 그래도 A, B를 35분 내에 다 해결한 것만 해도 굉장한 성과네요. 이 정도 실력을 계속 내준다면 레드를 올해 안에 찍을 수도 있겠습니다.