Educational Codeforces Round 150 (Rated for Div. 2)

A. Game with Board (0:06, +1)

$n$이 5 이상이면 Alice가 1을 두 개만 남기고 줄 수 있다. 그렇지 않은 경우에는 Bob이 항상 이긴다. 대충 생각했다 한 번 틀렸다.

 

B. Keep it Beautiful (0:11, +)

정렬된 상태인지 검사하고, 만약 깨진다면 그 뒤가 여전히 정렬된 상태이면서 첫 번째 수보다 작은지 계속 검사해주면 된다.

 

C. Ranom Numbers (0:32, +)

C치고 굉장히 어려웠다. 뭔가 그리디적인 방법을 시도해보고 싶지만, 그러다간 말리기 쉽다. 숫자 종류가 5개로 작으므로 모든 경우를 다 시도해보자. 우선 주어진 문자열에 대한 답을 계산한 후, 문자를 하나씩 바꿔볼 것이다. 문자를 바꾸면 이전에 위치한 문자들의 부호가 달라질 수 있는데, 이는 누적합으로 계산해줄 수 있다. 다만 범위를 계산하는 것이 조금 까다로우므로 주의하면 된다.

 

D. Pairs of Segments (0:55, +1)

지워야 하는 구간의 최소 개수는 연결할 수 있는 pair의 최대 개수를 구하면 된다. 구간들을 끝 점에 대한 오름차순으로 정렬한 후 , \(dp[x]\)를 \(x\)번째 구간까지 고를 수 있는 pair의 최대 개수로 정의하자. 그러면 겹치는 구간 \(i< j\) 에 대해 \(l = min(s_i, s_j)\)라 하고 \(y\)를 끝 좌표가 \(l\)미만인 마지막 구간이라 하면, \(dp[j]=max(dp[j],dp[y]+1)\)과 같은 식으로 계속 갱신해주면 된다. dp의 prefix max 꼴을 관리해야 하는데, 배열을 하나 더 만들거나 세그를 박으면 된다.

 

E. Fill the Matrix (1:32, +)

문제를 정리하면, 히스토그램 모양의 빈 공간에 해당하는 직사각형들을 너비 별로 구해야 한다. 우선 중요한 점은, 이를 높이가 1인 직사각형들로 분리하면 직사각형의 개수가 \(O(N^2)\)이 될 수 있어 이를 모두 저장할 수 없다. 따라서 같은 너비의 직사각형을 최대한 묶어주어야 한다. 각 직사각형의 왼쪽 위, 오른쪽 위 꼭짓점에서 양방향으로 레이저를 발사한다고 생각하면 \(O(N)\)개의 직사각형이 나오는데, 이를 스택, 세그, 또는 UF로 잘 구현해주면 된다. 모은 후에는 너비 내림차순으로 정렬한 후 그리디하게 빼주면 된다.

 

F. Monocarp and a Strategic Game (upsolved)

간단한 식 정리를 통해 문제를 다음과 같이 정리할 수 있다: \(x=a-b, y=c-d\)로 보았을 때 \(N\)개의 벡터 중 \(K\)개의 벡터를 골라 벡터의 크기를 최대화하여라. 어디서 본 문제인데, 시간도 없고 풀이도 정확히 몰라서 대회 시간 중에는 풀지 못했다. 여러 대회에 나온 적이 있는 문제이다. 풀이는 전자 링크에 가면 에디토리얼(일본어)에 잘 나와 있다. 요약을 하자면, 정답 벡터의 방향을 먼저 정하면 해당 벡터로부터 왼쪽 90도, 오른쪽 90도 범위 안에 있는 벡터만 더하는 것이 최적이다. 하지만 이를 일일이 해 볼 수는 없으니, 골라야 하는 벡터의 종류를 기준으로 보자. 이는 당연히 연속되므로 우선 \(O(N^2)\)에 문제를 해결할 수 있다. 이를 \(O(NlogN)\)에 해결하려면 투 포인터의 아이디어를 사용해야 한다. 구현 난이도가 방법에 따라 많이 차이나는 것 같은데, 벡터의 원래 방향을 저장하는 것이 아니라 삽입이랑 삭제에 대한 이벤트로 관리하면 편하다.