Codeforces Round 1039 (Div. 2)

B,C 난이도가..

C는 심지어 시스페일 당해서 더 슬펐다.

A — 00:06 AC#

각 시점에서 코인 없이 제거할 수 있는 쓰레기 중에 가장 무거운 쓰레기부터 그리디하게 처리하면 된다. 무게가 $c$를 넘어간 쓰레기는 다시 되돌릴 수 없고, 만약 1초 뒤에 무게가 $c$를 넘어가는 쓰레기가 있다면 그 쓰레기를 처리하는 게 이득이기 때문이다. 사실 무게가 $c / 2$ 초과인 쓰레기는 1초 뒤에는 코인이 있어야 제거할 수 있게 되므로 $c / 2 < x \le c$를 만족하는 $x$ 중에 아무거나 제거해도 된다.

B — 00:13 ~ 00:45 WA(2), TLE(3)#

문제를 잘못 읽어서 연속된 자연수 5개가 증가/감소하는 형태가 조건이라고 생각해 단순히 random하게 돌려도 풀리지 않을까 싶어 제출했다가 WA를 받았다. 심지어 테케1은 통과해서 페널티는 그대로 먹었다.. 이후 연속된 5개를 판별할 때 list를 slice해서 사용했는데 이걸 매 시행마다 하니까 $O(n)$에 쌓이고 쌓여 TLE를 받았다. 어떻게든 뚫릴까 싶어서 계속 시도했다가 -4 패널티라는 참사를 받고 그만뒀다.

C — 00:57 ~ 01:01 TLE(2)#

여기서도 TLE받으면서 멘탈이 반쯤 터졌다. 그땐 몰랐는데 하나의 원소로 힙에 많게는 몇백 번까지 push와 pop을 반복하는 막장 코드를 짰었다.

E1 — 01:22 AC#

누적합으로 $a[i] \ge v$를 만족하면 $+1$이고 아니면 $-1$로 계산한다면 특정 구간에 합이 0보다 클 때 그 구간 내에 있는 원소 중에 $\ge v$를 만족하는 게 더 많다는 뜻이므로 이를 활용하면 풀 수 있다. 가능한 중앙값의 최댓값은 이분탐색으로 찾을 수 있다. 웰노운?이라고 한다. parity 나누면 좋다.

D — 01:27 AC#

C를 TLE받고 E1을 풀기 전에 D 지문을 잠깐 읽었었고, E1 풀면서 아이디어가 떠올라서 구현은 막힘없이 했다.

각 위치에서 시작하는 LDS의 길이를 저장할 배열을 하나 만들고, 오른쪽부터 왼쪽으로 돌면서 $p[i] > p[i+1]$이면 $a[i] = a[i+1] + 1$로 정해주면 $O(n)$에 구할 수 있다. 그럼 각 위치에서 시작하는 LDS 길이가 $a[i]$가 되고, 1부터 $a[i]$까지 전부 더해준 게 길이 합이 된다.

따라서 배열 $a$의 $i$번째 원소에 대해 $a[i] \times (a[i] + 1) / 2$로 계산할 수 있고, 모든 원소에 대해 저 값을 계산한 합이 정답이 된다.

B — 01:45 AC#

연속된 5개를 매번 slice하지 않고, 현재 값과 이전 4개 값 $a, b, c, d$를 직접 판별 함수에 인자로 넣어서 어떻게든 잘 돌아가게 만들었다. 기본적으로 L을 선택하되, 연속된 5개가 증가, 감소인지 확인해서 왼쪽과 오른쪽 중 하나만 가능하면 당연히 그쪽을 선택해야 하고, 둘 다 가능하면 L을 선택했을 때와 R을 선택했을 때를 한 번 더 확인해서 나쁜 배열이 되지 않도록 했다. 친구도 끝나고 B 난이도에 대해 의문을 제기했을 정도로 구현과 아이디어?면에서 어려운 문제였다.

C — 01:59 AC → TLE(System testing)#

최대한 push, pop을 하는 빈도를 줄이고, 세그트리 사용해서 쿼리 갱신하는 횟수도 줄였다. 어떻게든 커팅해서 2000ms 제한에 1964ms로 AC를 받긴 했으나.. 더 나은 방법을 찾지는 못했고 그렇게 대회가 끝나고 시스텟에서 TLE로 터져버렸다.

사실 문제의 정해는 애초에 이런 게 아니라, 왼쪽부터 $a[i] < x$인 곳에 $x$를 더하기 때문에 $b$의 어떤 시점에서 구간 $[1, k-1]$에 대해 $\min(b[1, k-1]) \times 2 \le b[k]$를 만족하는 $k$가 존재하면 한 번에 만들 수 있는 최댓값을 초과하기 때문에 무조건 NO가 된다는 발상이 필요했다. 유의미한 관찰을 하지 못한 게 아쉬운 문제다.