[알고리즘] Codeforces Round #771 (Div. 2)

민트를 복구할 수 있는 기회였는데 아쉽게 실패하고 말았다.

3솔에 블루퍼포가 나와서 싱글벙글하고 있었는데 B가 TLE로 터져버렸다.

알고보니 sys.stdin.readline을 쓰지 않아 생긴 문제였다.

C문제도 같은 이유로 프리테스트에서 TLE가 발생했지만 B에서도 나올줄은 전혀 몰랐다. (두 문제 모두 $O(n)$으로 해결했었다.)

앞으로는 확인을 꼼꼼히 해야겠다.

(후에 라인 추가로 AC받긴 했다.)

파이썬당했다.

A - Reverse [Solved!]

배열의 중간 일부 구간을 뒤집었을 때 사전순으로 가장 앞서는 배열을 출력하는 문제이다.

 

인덱스와 배열값이 다른 부분이 나오는 곳부터 그 이후에 나오는 최솟값이 있는 곳까지 뒤집으면 된다.

 

B - Odd Swap Sort [Solved?]

배열에서 연속한 두 원소의 합이 홀수이면 서로를 바꿀 수 있다. 이를 여러번 시행하여 오름차순으로 만들 수 있는지 확인하는 문제이다.

 

우선 연속한 원소의 홀짝이 같으면 더했을 때 짝수가 되므로 서로를 바꿀 수 없다.

이는 연속하지 않아도 성립한다.

예를 들어 $(3,2,2,2,1)$에서 $3,1$은 서로 바꿀 수 없다.

즉 위 배열같은 모양은 오름차순을 만들 수 없다는 말이다.

배열에서 홀수 원소들로 이루어진 배열과 짝수 원소들로 이루어진 배열을 각각 구해 둘 다 이미 오름차순일 때 오름차순을 만들 수 있다.

 

C - Inversion Graph [Solved!]

배열을 이용해서 그래프를 만든다. $i<j$일 때 정점 $p_i, p_j$은 같은 그래프에 속한다. 이 때 그래프의 연결된 요소 수를  구하는 문제이다.

 

우선 배열에서 최댓값이 나오면 최댓값 이후는 모두 같은 요소에 속한다.

그래서 최댓값 배열을 전처리했다.

배열이 $(3,1,5,2,4)$라면 $(3,3,5,5,5)$가 나온다.

그 후 배열을 순회하며 최댓값이 변하는 부분에서 1을 추가하면 된다.

다만 변하는 부분의 인덱스가 현재 최댓값보다 작다면 이후에 연결된 정점이 더 나온다는 말이므로 1을 뺀다.

예를들어 위의 배열에서 처음 최댓값은 $3$이지만 2번째에서 변했다.

그리고 뒤에 나온 $2$는 $3$과 같은 요소에 속하기 때문에 1을 빼는 것이다.