Codeforces Round #710 (Div. 3)

Expert라 언레다. 푼 사람 수를 보면 F,G도 풀었어야하는데 좀 아쉽다.

 

A. Strange Table

n x m 행렬 A에서 A_ij 를 알 때, A_ji를 구하는 문제. 행과 열을 나눈 몫과 나머지를 다시 조합해서 해결.

 

B. Partial Replacement

주어진 문자열에서 정해진 위치만 x로 바꿀 수 있다. 최소한으로 바꿔서 각 x들 사이 거리가 k 미만이 되도록 하는 문제. 왼쪽 끝과 오른쪽 끝은 문제에서 무조건 바꾸라고 하였으니 그대로 바꾼다. 양 끝의 바뀐 x들 사이를 순회하면서, 길이가 k 이상이 되는 지점 직전을 교체해 나간다. 왼쪽 끝과 오른쪽 끝 사이 길이는 고정이니, 어떻게 바꾸던지 (r-l+1)/k 개 교환됨은 자명하다.

 

C. Double-ended Strings

문자열의 맨 앞 글자 또는 맨 뒷 글자를 제거할 수 있다. 최소한으로 제거하여 두 문자열이 일치하게 만드는 문제. 두 문자열의 길이가 20으로 매우 짧으므로, 첫 번째 문자열의 모든 substring, 두 번째 문자열의 모든 substring을 비교할 수 있다. 가능한 긴 공통 substring을 찾으면 된다.

 

D. Epic Transformation

주어진 수열에서 서로 다른 임의의 두 원소를 고르고, 고른 둘을 없앨 수 있다. 만들 수 있는 수열의 최소 크기를 구하는 문제. 해석해보면 www.acmicpc.net/problem/19590 이 문제와 일치한다. 즉, 수열에서 가장 많은 원소가 절반 이하면 무조건 가능하고, 절반 이상이면 절반을 넘는 만큼 남는다.

 

E. Restoring the Permutation

주어진 수열에서 원소의 값이 바뀌었다는 것은 원본 수열의 해당 위치가 새로운 최댓값이라는 뜻이며, 그렇지 않다는 것은 원본 수열의 해당 위치에 현재 최대값 이하의 원소가 있다는 뜻이다. 수열의 값이 바뀌는 지점에서는 원본 수열의 값이 자명하므로 고정하고, 남은 위치들을 조건에 맞게 적절히 채워 나가면 된다. 최소 수열을 만드려면, 가능한 작은 값을 앞에서부터 채워 나가면 된다. 한편, 최대 수열의 경우는 가능한 큰 값을 앞에서부터 채워 나가야 하는데 현재 최댓값 이하의 원소가 있어야 하므로, set을 사용해 upper_bound-1 값으로 채워 나가면 된다.