Educational Codeforces Round 69 (Rated for Div. 2)

https://codeforces.com/contest/1197/standings/participant/26546079#p26546079

일단 오렌지 복귀는 했으니 잘한걸로..?

 

A. DIY Wooden Ladder

가장 큰 두개를 수직선으로 삼으면 된다.

 

B. Pillars

max에서 시작해서 투포인터로 퍼저나가는 방법을 썼다. maximum이 global maximum인지 확인하는 방법이 더 좋고 편한 방법같다. n-1을 찾고  - n-2를 찾고 - ...식으로 생각해서 이런 풀이가 나왔던거 같다. 쉬운 문제여서 다행히 큰 상관은 없었다.

 

C. Array Splitting

처음에 a_i >= a_i-1를 못보고 whining하고있었다. 조건을 잘 읽자..

division하는 operation이 cost를 얼마나 감소시키는지 생각하면 쉽다.

 

D. Yet Another Subarray Problem

처음에 딱 보고 거의 maximum subarray problem이네? 라는 생각이 들었다. 차이점은 긴 subarray를 고르는 것에 대한 페널티가 있고, 이 페널티는 subarray길이가 m단위 안에서 증가할땐 바뀌지 않는다. 이런 상황에서는 m단위를 하나의 원소로 생각하고 maximum subarray problem을 그대로 돌리면 된다는 생각이 들었다.

 

내 풀이는 그냥 첫 m개의 점에 대해, 그 점에서부터 시작해 원소를 m개씩 끊어서 보는 maximum subarray problem을 돌리는 것이다. m개씩 끊어진 구간의 값은 (전체의 합-k). 이 구간 안에서는 어떻게 골라도 코스트가 k니까 이렇게 한다고 생각하면 된다. maximum subarray problem과 다른 점은 구간을 한개의 원소로 볼때, 구간 전체의 합과 구간 맨 처음에서 시작해 얻을수 있는 최댓값은 다른데, 이 최댓값을 취하면 뒤쪽의 다른 구간이랑 이어지지는 않아 완전한 한개의 원소로 볼 수는 없지만 이걸 취하는 게 최선일 수 있다. 이 케이스를 잘 처리해주면 된다.

 

E. Culture Code

대회 중

우선 문제가 제한 있는 회의실 배정의 경우의 수 문제로 생각할 수 있다는 걸 깨달았다.(아래는 모두 회의실 배정의 언어로 문제를 설명한다.) 일반 회의실 배정은 회의 숫자를 최대화하는 거지만, 이건 마지막 회의가 끝날 때까지 비어있는 시간을 최소화함과 동시에 더 이상 추가될 수 있는 회의가 없는 케이스를 찾고 그러한 케이스들을 세는 거라 제한이 확 많아졌고 그래서 어떻게 접근할지 막막했다.

 

깊은 고민 끝에 뭔가 끝점 순으로 정렬해놓고 dp를 돌리면 일단 가장 작은 비어있는 시간을 구할 수 있을 거 같았고, 뭔가 좌표압축과 기묘한 dp점화식이 짬뽕된 코드를 짜놓고 당연히 WA를 받았다. 일단 큰 문제점 중 하나는 한 구간을 볼때 왼쪽에 있는 구간들 중 비어있는 시간을 최소화 할 수 있는 것들을 모두 골라야 하는데, 그러지 않고 딱 왼쪽 점에 있는 dp값 하나만 보고 있는 것 같다. 이걸 해결할려면 왼쪽에 있는 구간들 중에, 그걸 골랐을 때 거리가 최소가 되는지 여부를 판단해야 하는데, 대회중에 짰던 코드 베이스로 그걸 고쳐낼 수가 없었다. (그리고 아마 이 문제가 끝이 아닐 것이다.)

 

아마 D번까지 대회가 너무 잘 풀려서 멘탈이 오버플로우나서(?) 그냥 생각이 아무것도 안됐던 것 같다. 이러다가 결국 마이너스 레이팅 변화 본게 몇번 있었던거 같은데 너무나 다행히도 이번 E번이 꽤 어려운 편이라 그러지는 않았다. 이런 멘탈문제도 진짜 고쳐야..

 

업솔빙

에디토리얼과 좀 다른 바법이다. 에디토리얼은 내가 이해를 못하겠다.

 

구간에는 그 구간의 왼쪽으로 구간들을 이었을 때 얻을 수 있는 경우의수와 최소거리가 저장하고자 한다고 하자.  왼쪽에서 오른쪽으로 구간들을 훑으면서 왼쪽 구간을 봐 경우의수와 최소거리를 업데이트해야 하니, 구간의 왼쪽 끝이 단조증가해야 뭔가 구간관리가 될 거 같아서 우선 구간을 왼쪽 끝으로 정렬한 array를 준비했다. 그러면 어떤 구간을 볼때 그 구간의 왼쪽에 어떤 구간과 이어야 최소 거리를 얻을 수 있을까.. 라는 질문이 나오는데, 생각해보면 구간의 왼쪽 끝이 정해졌으면 거기서 왼쪽으로 이었을 때 달성할 수 있는 최소 거리(그리고 그러한 경우의 수)도 정해져 있다.

 

이건 왼쪽 끝을 왼쪽에서 오른쪽으로 보며 관리할 수 있다. 정확히는, 보고 있는 왼쪽 끝이 늘어날 때마다, 그 왼쪽 끝보다 오른쪽 끝이 작은 구간들을 새로 이을 수 있는데 이 구간들을 이었을 때 새로운 최단거리와 새로 얻는 경우의수를 그 새로 이을 구간에 저장해놓은 경우의수/최소거리/새로 이을 구간의 위치로 계산할 수 있다. 이걸 토대로 왼쪽 끝이 늘어날 때 그 새로운 왼쪽 끝에서부터 왼쪽으로 이을 떄 얻을 수 있는 최단거리와 경우의 수를 구할 수 있다.

 

오른쪽 끝으로 정렬된 구간들도 준비해두고 포인터를 하나 관리하면 새로 추가되는 [왼쪽 끝의 왼쪽으로 새로 이을 구간] 만 볼 수 있기 때문에 어레이를 훓는 시간복잡도도 O(n)으로 유지된다.

 

마지막에 답을 구할때 오른쪽으로 더 이상 이을게 없는 구간들의 경우의 수를 가져와야 하는데, 이때 최소거리가 최소인 것들만 가져와야 한다. 위 문단에서 말한 오른쪽 끝으로 정렬된 구간을 관리하는 포인터 뒤쪽으로만 보면 된다. (포인터 앞에 있는 것들은 그 구간 오른쪽에 어떤 구간이 존재하니까 포인터 앞으로 가게 된 거니까)

 

에디토리얼에서 얻은 아이디어인데, 비어있는 거리가 최소화되어 있으면 그러한 subset은 big enough subset이다. 사실 big enough subset여부를 따로 체크하지 않았는데 이러한 property덕분에 다행히 통과된 거 같다.

 

총 시간복잡도는 초기의 정렬에 드는 O(nlogn). 대회 중에는 더러운 문제 같아 보였는데 막상 업솔빙할땐 아이디어도 꽤 빨리 나왔고 구현도 그리 어렵지 않았다. 크게

1. 비어있는 시간을 최소화하기 위해 왼쪽 끝으로 정렬 후 dp

2. 왼쪽에 추가되는 구간을 추적하기 위해 반대로 정렬된 배열 관리

3. 최종적으로 답 합산 및 출력

이정도 과정을 거친거 같은데 뭔가 대회중에 2를 해야 한다는 자각 없이 1을 하니까 코드가 이상해지고 망했던 거 같다. 음.. 내일은 더 나아졌으면 좋겠다.