Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2)

https://codeforces.com/contest/2084

 

 

두 시간의 지옥을 경험한 끝에 E를 겨우 풀면서 마이너스 델타를 면했다. 요즘 왜인지는 모르겠으나 구현력이 상승하면서 코드 짜는 게 시원시원해졌다. 

 

Prob. A

홀수는 쉽고 짝수는 믿자.

 

Prob. B

별 생각 없이 정렬을 하고 보니까 풀이가 보였다.

 

Prob. C

홀수일 때 가운데 처리해 주고, 나머지를 그냥 점대칭으로 만들어주면 된다.

 

Prob. D

대충 체커를 생각해 보면 길이가 $K$인 구간들로 같은 수들을 커버하려고 할 거니까 그게 힘들게끔 같은 수의 간격을 $K$ 이상으로 만들어주면 된다. 문제 상황이 너무 헷갈렸다.

 

Prob. E

하아... 일단 특정 mex 값의 경우의 수를 구하는 건 어려워 보이니까 mex가 특정 값 $k$보다 큰 경우의 수를 구하는 걸로 바꾸자. 여기서부턴 가능한 접근 방법이 엄청 많다. 처음에 시도한 방법은 $k$를 $0$부터 늘려가면서 확실히 포함해야 하는 구간을 관리하고, ? 중 가장 왼쪽을 고정하고 가능한 오른쪽에 대한 값의 합을 누적합으로 구하는 것이었다. 그런데 열심히 식정리를 하고 보니 누적합을 어떻게 해도 도저히 가능한 꼴이 아니었다. 그러고 나서는 수많은 방식으로 접근하다가 세제곱이란 걸 깨닫기를 반복했고, 멘탈이 점점 갈려나갔다. D까지만 해도 레드를 갈 만한 퍼포였으나 어느새 오렌지 강등을 걱정해야 하는 상황이 되고 말았다. 그러다가 아예 관점을 바꿔서 모든 구간에 대해 값의 합을 누적합으로 구해보자, 하는 생각이 들었다. 그래서 식을 써보니 이론적으로는 가능한 것 같은 꼴이 나왔으나, 가능한 mex 값을 구하기 위한 이분탐색이 어려워 보였다. 이는 mex 별로 구간의 합집합을 기록해놓고, ?에 대한 누적합도 만들어서 잘 케웍을 하면 될 것 같았다. 풀이가 맞는지는 뒤로 하고 일단 열심히 짜보니까 예제가 나왔고, 맞았다.