링크 : http://codeforces.com/contest/723
A : The New Year: Meeting Friends
세 사람이 있는 수직선 위의 세 지점이 주어지고, 모두의 이동거리의 합이 최소가 되는 약속지점을 찾는 문제이다. 교내대회에서 유사한 문제를 풀어본 적이 있어서 금방 해결할 수 있었다. 위치를 정렬했을 때 중간값이 되는 지점을 찾아야 하는데, 입력이 항상 3개라 조건문으로도 찾을 수 있겠지만 코드를 빨리 작성하려고 std::sort()를 사용하여 해결했다.
B : Text Document Analysis
주어지는 문자열에서 괄호 밖에 있는 단어 중 가장 긴 단어와, 괄호 안에 있는 단어의 개수를 구하는 문제.
괄호 안에 있는 단어 수를 셀 때, 언더스코어 또는 여는 소괄호 다음에 나오는 단어를 카운팅하는 것으로 간단하게 짤 수 있었다.
C : Polycarp at the Radio
문제를 이해하지 못해서 시간만 소비하고 포기...
D : Lakes in Berland
물과 육지를 나타내는 2차원 배열이 입력으로 주어지고, 호수의 개수를 주어진 수로 줄일 때 메워야 하는 영역의 최소 수를 구하는 문제이다.
먼저 호수와 바다를 구분하기 위해 바깥쪽에 있는 물을 따로 표시했다. 최대 입력의 크기인 50x50보다 더 큰 52x52 배열을 만들고 바깥의 물을 BFS하여 바다로 표시했다.
그리고 안쪽의 물 역시 BFS를 사용하여 영역의 개수를 세고, 각 영역의 크기와 시작점을 구조체로 저장해 두었다. 그리고 영역크기 순으로 소팅하여 작은 것부터 채우는 것으로 코드를 작성하였다.
A, B, D를 풀고 C도 풀어보려다가 시간이 다 되어 E, F번 문제는 못 풀어보았다..
Rank : 640
Rating : 1456 -> 1531 (+75)