Codeforces Round #516 (Div. 1)

A - Oh Those Palindromes

100,000자리의 문자열이 주어질 때 문자들을 잘 조합하여 만든 문자열의 부분문자열의 팰린드롬의 개수가

최대가 되게 하는 문자열을 구하는 문제이다.

이는 문자열 내의 문자들을 정렬하여 출력하면 된다. 생각해보면 이 방법이 답이라는 것을 쉽게 유추할 수 있다.

B - Labyrinth

시작점이 주어지고 왼쪽, 오른쪽으로 갈 수 있는 횟수가 정해져있을 때

주어진 매트릭스에서 몇 개의 칸에 도달할 수 있는 지를 구하는 문제이다.

queue<pair<pair<int,int>, pair<int,int> > > 를 선언하여

각각 { {y좌표, x좌표}, {왼쪽으로 갈 수 있는 횟수, 오른쪽으로 갈 수 있는 횟수} }를 담을 것이다.

위아래로 움직이는 것은 상관이 없으므로 처음에 시작 할 때 시작점에서 시작하여 갈 수 있는 위, 아래 칸들을 큐에 넣은 뒤

BFS를 돌려주며 왼쪽, 오른쪽으로 갈 수 있는 횟수가 남아있을 경우 이동하며

벽이 아니고 도달한 적이 없는 칸일 경우 위, 아래 칸들도 함께 큐에 넣어주며 반복해준 뒤

도달한 칸을 세어주면 답을 구할 수 있다.

 

C - Dwarves, Hats and Extrasensory Abilities

최대 30개의 좌표를 순차적으로 물을 때 마다 'black' 또는 'white'라고 답을 할 때

이들을 분리할 수 있는 직선의 두 점을 구하면 되는 문제이다.

만일 y좌표의 제한이 0 ~ 8일 경우 처음에 (0,x)을 물어 봤을 때 'black'일 경우

y | 0 1 2 3 4 5 6 7 8

     b

이 되며 다음에는 (4,x)를 물어봤을 때 'white'일 경우

y | 0 1 2 3 4 5 6 7 8

     b         w

가 되어 다음에는 (2,x)를 물어보면 되며, 만약 (4,x)를 물어봤을 때 'black'인 경우

y | 0 1 2 3 4 5 6 7 8

     b         b

이 되어 다음에는 (7,x)를 물어보면 될 것이다. 예를 들어 'white', 'white', 'black', 'black' 순으로 답했을 경우

y | 0 1 2 3 4 5 6 7 8

     w         w b b 

이 되며 선을 4와 5사이에 그으면 된다는 것을 알 수 있다.

위의 예시에서 4개의 답변에 대하여 0 ~ 2^3까지의 좌표가 필요하였는데

30개의 답변에 대하여 표시하려면 2^29 이기에 문제에서 제시된 범위인 10^9보다 작은 것을 알 수 있기에

이와 같이 풀 수 있다는 것을 알 수 있다.

즉 이분탐색을 이용하여 (0, x)의 색과 같으면 lo = mid, 다르다면 hi = mid로 변환해주며

같은 x축 하나에 'black'과 'white'를 나눌 수 있다.

이 때 w와 b를 나누기 위하여 (y , x+1) (y-1, x-1)와 같이 사선으로 직선을 긋는다면 정확히 나눌 수 있으므로

이를 출력해주면 되는 문제이다.

D - Candies for Children

X

E - Lasers and Mirrors

X

F - String Journey

X