Codeforces Round 1039 (Div. 2)

B,C 난이도가..

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

 

A 00:06 AC

각 시점에서 코인 없이 제거할 수 있는 쓰레기중에 가장 무거운 쓰레기부터 그리디하게 처리하면 된다. 무게가 c를 넘어간 쓰레기는 다시 되돌릴 수 없고, 만약 1초 뒤에 무게가 c를 넘어가는 쓰레기가 있다면 그 쓰레기를 처리하는게 이득이기 때문이다. 사실 무게가 c/2 이상인 쓰레기는 1초 뒤에는 코인이 있어야 제거할 수 있게되므로 c/2 < x <= 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] >= v 를 만족하면 +1이고 아니면 -1로 계산한다면 특정 구간에 합이 0보다 클 때 그 구간 내에 있는 원소중에 >= 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]*(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])*2 <= b[k] 를 만족하는 k가 존재하면 한번에 만들 수 있는 최댓값을 초과하기 때문에 무조건 NO가 된다는 발상이 필요했다. 유의미한 관찰을 하지 못한게 아쉬운 문제다.